APCS202101 第2題流量

有 n 個伺服器編號 0 到 n−1，以及 m 個城市編號 0 到 m−1，已知第 i 個伺服器要傳送到城市 j 的流量為 Q[i][j]。

工程師們在規劃每個伺服器應該要放在哪個城市，對於一個方案 c=(c1,c2,c3,…cn)，表示編號 i 的伺服器要放在城市 ci。

城市之間資料傳輸是需要費用的，若城市u 要傳送 f 的流量到城市 v，費用的計算方式如下：

若 u=v，每單位流量需要花 1 塊錢。

若 u≠v，小於等於 1000 的流量每單位要 3 塊錢，大於 1000 的部份每單位 2 塊錢。

若城市u 有多個伺服器都要傳送流量到城市 v，會先將這些起點終點相同的傳輸流量相加再計算花費。

工程師們總共提出了 k 種方案，請你找到花費最少的方案所需的費用。

輸入說明

第一行包含三個整數 n,m,k。接下來 n 行每行有 m 個整數，第 i 行的第 j 個數字為 Q[i][j]。接下來有 k 行，每行有 n 個整數，表示一個方案。

配分 20分: n=1,k=1,1≤m≤50

30分: n=1,1≤m,k≤50

50分:1≤n, m,k≤50

輸出說明

輸出費用最小的方案所需的花費。

輸入範例

2 3 3

30 23 23

5 25 3

0 0

0 1

0 2

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

輸出範例

217

13470

測資說明

第一組

將伺服器放置在0 0，第0台伺服器放置在第0個城市，第1台伺服器放置在第0個城市，伺服器都在第0個城市，將相同目標城市的流量相加，伺服器所在城市會影響流量的來源城市。

(30+5)*1+(23+25)*3+(23+3)*3=257

將伺服器放置在0 1，第0台伺服器放置在第0個城市，第1台伺服器放置在第1個城市，伺服器在不同城市，流量不需要相加。

30*1+23*3+23*3 = 168 , 5*3+25*1+3*3 = 49 , 168+49=217

將伺服器放置在0 2，第0台伺服器放置在第0個城市，第1台伺服器放置在第2個城市，伺服器在不同城市，流量不需要相加。

30*1+23*3+23*3 = 168 , 5*3+25*3+3*1 = 93 , 168+93=261

答案：217

解題策略

伺服器會隨著輸入而放置在不同城市，會影響費用計算的來源城市，需先將相同到達城市的流量累加起來，使用map與deque，相同城市的伺服器放在同一個deque，累加所有伺服器在同一個城市的流量，再根據條件計算費用。