# APCS實作題2021年1月第2題：流量 > 日期：2023年9月15日 > 作者：王一哲 > 題目來源：110年1月實作題第2題 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f606) <br /> ## 題目 ### 問題描述 有 $n$ 個伺服器編號 $0$ 到 $n-1$，以及 $m$ 個城市編號 $0$ 到 $m-1$，已知第 $i$ 個伺服器要傳送到城市 $j$ 的流量為 $Q[i][j]$。 工程師們在規劃每個伺服器應該要放在哪個城市，對於一個方案 $c = (c_1, c_2, c_3, \dots, c_n)$，表示編號 $i$ 的伺服器要放在城市 $c_i$。 城市之間資料傳輸是需要費用的，若城市 $u$ 要傳送 $f$ 的流量到城市 $v$，費用的計算方式如下： - 若 $u = v$，每單位流量需要花1塊錢。 - 若 $n \neq v$，小於等於1000的流量每單位要3塊錢，大於1000的部份每單位2塊錢。 若城市 $u$ 有多個伺服器都要傳送流量到城市 $v$，會先將這些起點終點相同的傳輸流量相加再計算花費。 工程師們總共提出了 $k$ 種方案，請你找到花費最少的方案所需的費用。 <br /> ### 輸入說明 第一行包含三個整數 $n, m, k$。 接下來 $n$ 行每行有 $m$ 個整數，第 $i$ 行的第 $j$ 個數字為 $Q[i][j]$。 接下來有 $k$ 行，每行有 $n$ 個整數，表示一個方案。 配分 - 20分：$n = 1, k = 1, 1 \leq m \leq 50$ - 30分：$n = 1, 1 \leq m, k \leq 50$ - 50分：$1 \leq n, m, k \leq 50$ <br /> ### 輸出說明 輸出費用最小的方案所需的花費。 <br /> ### 範例一：輸入 ``` 2 3 3 30 23 23 5 25 3 0 0 0 1 0 2 ``` ### 範例一：正確輸出 ``` 217 ``` <br /> ### 範例二：輸入 ``` 3 4 5 500 400 800 200 500 400 100 600 450 420 800 790 0 0 0 0 1 2 0 2 2 2 1 2 1 1 1 ``` ### 範例二：正確輸出 ``` 13470 ``` <br /> ## Python 程式碼 於 ZeroJudge 測試結果，最長運算時間約為 0.1 s，使用記憶體最多約為 3.4 MB，通過測試。 ```python= n, m, k = map(int, input().split()) # 讀取n, m, k Q = [] # 儲存傳輸量資料的串列 for _ in range(n): # 讀取n行傳輸量資料 Q.append(list(map(int, input().split()))) fees = [0]*k # 各種方案的費用 for x in range(k): # 讀取k行的方案 servers = list(map(int, input().split())) # 各個伺服器位在的城市編號 cross = [[0]*m for _ in range(m)] # 跨城市傳輸的流量 for i in range(n): # 讀取 Q[i][j] for j in range(m): if servers[i] == j: # 若伺服器與目標在同一座城市 fees[x] += Q[i][j] # 費用加上流量 else: # 若伺服器與目標在不同城市 cross[servers[i]][j] += Q[i][j] for i in range(m): # 讀取跨城市傳輸的流量 for j in range(m): if cross[i][j] <= 1000: # 流量小於等於1000的算法 fees[x] += cross[i][j]*3 else: # 流量大於1000的算法 fees[x] += 3000 + (cross[i][j]-1000)*2 print(min(fees)) # 印出答案 ``` <br /><br /> 修改取最小值的方法，計算完一個方案的費用時立刻更新最小值。於 ZeroJudge 測試結果，最長運算時間約為 0.1 s，使用記憶體最多約為 3.4 MB，通過測試。 ```python= import sys n, m, k = map(int, input().split()) # 讀取n, m, k Q = [] # 儲存傳輸量資料的串列 for _ in range(n): # 讀取n行傳輸量資料 Q.append(list(map(int, input().split()))) ans = sys.maxsize # 最低費用，預設為最大值 for x in range(k): # 讀取k行的方案 servers = list(map(int, input().split())) # 各個伺服器位在的城市編號 cross = [[0]*m for _ in range(m)] # 跨城市傳輸的流量 fee = 0 # 此方案的費用 for i in range(n): # 讀取 Q[i][j] for j in range(m): if servers[i] == j: # 若伺服器與目標在同一座城市 fee += Q[i][j] # 費用加上流量 else: # 若伺服器與目標在不同城市 cross[servers[i]][j] += Q[i][j] for i in range(m): # 讀取跨城市傳輸的流量 for j in range(m): if cross[i][j] <= 1000: # 流量小於等於1000的算法 fee += cross[i][j]*3 else: # 流量大於1000的算法 fee += 3000 + (cross[i][j]-1000)*2 # 若此方案費用更低則更新答案 ans = min(fee, ans) # 印出答案 print(ans) ``` <br /><br /> ## C++ 程式碼 於 ZeroJudge 測試結果，最長運算時間約為 3 ms，使用記憶體最多約為 340 kB，通過測試。 ```cpp= #include <iostream> #include <climits> #include <algorithm> using namespace std; int main() { int n, m, k; cin >> n >> m >> k; // 讀取n, m, k int Q[n][m]; // 儲存傳輸量資料的陣列 for(int i=0; i<n; i++) { // 讀取n行傳輸量資料 for(int j=0; j<m; j++) { cin >> Q[i][j]; } } int ans = INT_MAX; // 最低費用，預設為最大值 for(int x=0; x<k; x++) { // 讀取k行的方案 // 各個伺服器位在的城市編號 int servers[n]; for(int y=0; y<n; y++) { cin >> servers[y]; } // 跨城市傳輸的流量 int cross[m][m]; for(int y=0; y<m; y++) { for(int z=0; z<m; z++) { cross[y][z] = 0; } } int fee = 0; // 此方案的費用 for(int i=0; i<n; i++) { // 讀取 Q[i][j] for(int j=0; j<m; j++) { if (servers[i] == j) { // 若伺服器與目標在同一座城市 fee += Q[i][j]; // 費用加上流量 } else { // 若伺服器與目標在不同城市 cross[servers[i]][j] += Q[i][j]; } } } for(int i=0; i<m; i++) { // 讀取跨城市傳輸的流量 for(int j=0; j<m; j++) { if (cross[i][j] <= 1000) { // 流量小於等於1000的算法 fee += cross[i][j]*3; } else { // 流量大於1000的算法 fee += 3000 + (cross[i][j]-1000)*2; } } } // 若此方案費用更低則更新答案 ans = min(fee, ans); } cout << ans << endl; // 印出答案 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`