f606 - 2. 流量
題目描述
題目給定 $n$ 個伺服器和 $m$ 個城市，以及伺服器到城市的流量 $Q[i][j]$。有 $k$ 種伺服器放置方案，每種方案指定每個伺服器放置在一個城市。目標是找到花費最少的方案，其中城市間的傳輸費用根據流量大小和城市是否相同而定。
解題思路
程式碼模擬了 $k$ 種方案，並計算每種方案的總費用。對於每種方案，程式碼首先計算每個城市接收到的總流量。然後，根據流量大小計算城市間傳輸的費用：如果流量小於等於 1000，則每單位流量的費用為 3；否則，小於等於 1000 的流量費用為 3，超過 1000 的流量費用為 2。程式碼遍歷所有方案，並記錄最小費用。
複雜度分析
- 時間複雜度: O(k * n * m^2)
- 空間複雜度: O(m^2)
程式碼
#include <iostream>
using namespace std;
int n,m,k,q[51][51],ans=10000001,f[51][51];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m >> k;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin >> q[i][j];
while(k--){
for(int i=0;i<m;++i)
for(int j=0;j<m;++j)
f[i][j]=0;
int tn,tmp=0;
for(int i=0;i<n;++i){
cin >> tn;
tmp+=q[i][tn];
for(int j=0;j<m;++j)
if(tn!=j)f[tn][j]+=q[i][j];
}
for(int i=0;i<m;++i){
for(int j=0;j<m;++j){
if(f[i][j]>1000)
tmp+=f[i][j]*2+1000;
else
tmp+=f[i][j]*3;
}
}
ans=min(tmp,ans);
}
cout << ans ;
}