主題

ZeroJudge - f606: 2. 流量 解題心得

Not In My Back Yard | 2021-01-22 09:00:05

題目連結:


題目大意:
輸入第一列給定三正整數 n 、 m 、 k (1 ≦ n 、 m 、 k ≦ 50),代表有 n 個伺服器(編號 0 ~ n - 1)、 m 座城市(編號 0 ~ m - 1)以及 k 個伺服器放置方案。

接著有 n 列輸入,每列給定 m 個非負整數,代表這 n 個伺服器到 m 個城市的預計流量。再接著有 k 列輸入,每列給定 n 個非負整數,代表在此方案下每個伺服器要分配到哪個城市。

假設有伺服器的城市 u 有流量到城市 v (若有多個伺服器有起點、終點一樣的流量路徑,則先將這些路徑合併再做其他計算),則:
當 u = v 時,則每單位流量需要花 1 元;
當 u ≠ v 時, ≦ 1000 之部分每單位 3 元 、 > 1000 之部分則變為每單位 2 元。

試問給定的 k 個方案中哪個方案之總成本最小,其值為何?



範例輸入:
範例輸入 #1
2 3 3
30 23 23
5 25 3
0 0
0 1
0 2

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


範例輸出:
範例輸出 #1
217

範例輸出 #2
13470


解題思維:
模擬每個方案即可。

將伺服器到每個城市的流量存為一個 n × m 二維陣列 F,其中 F[i][j] 代表伺服器 i 對城市 j 之流量。接著再令一個 m × m 二維陣列 M 儲存每個方案下,每個城市彼此之間的流量。

接著對於每個方案跑過每個伺服器,看它們(假設現在是第 S 個伺服器)被分配到哪個城市(假設為 C),就將該伺服器所有流量的「開頭」設為 C 。所以 M[C][0] 、 M[C][1] 、…… 將會依序加上 F[S][0] 、 F[S][1] 、 ……。跑完所有伺服器之後,掃過一次 M 陣列,根據題目的條件式算出目前方案的總成本。

而所有方案裡面總成本最小之值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
110 巴幣: 0

創作回應

更多創作