p010. 2. 流量 - KitaJudge | 高雄市資訊培育協會線上程式解題系統

內容

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

工程師們在規劃每個伺服器應該要放在哪個城市，對於一個方案 c=(c₁,c₂,c₃,…c_n)，表示編號 i 的伺服器要放在城市 c_i。

城市之間資料傳輸是需要費用的，若城市 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

輸出說明

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

範例輸入 #1

範例輸出 #1

範例輸入 #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

範例輸出 #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

標籤:

出處:

2021年1月 APCS [管理者：

zero (管理員)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」