流量 (APCS 2021-01 中級)

有 \(n\) 台伺服器，編號為 \(0\) 到 \(n-1\)；另有 \(m\) 座城市，編號為 \(0\) 到 \(m-1\)。

伺服器 \(i\) 必須傳送資料到每一座城市。已知 \(Q[i][j]\) 表示伺服器 \(i\) 要傳送到城市 \(j\) 的流量。

工程師提出了 \(k\) 個伺服器配置方案。每個方案包含

其中 \(c_i\) 表示伺服器 \(i\) 放在城市 \(c_i\)。伺服器放置的城市就是資料傳輸 的起點，資料要送達的城市則是終點。

對一個方案計算費用時，必須先把起點城市與終點城市都相同的流量加總。 也就是說，從城市 \(u\) 傳到城市 \(v\) 的總流量為

不同起點的流量不能合併。得到 \(F[u][v]\) 後，再依下列規則計算這一批流量 的費用：

• 若 \(u=v\)，每單位流量費用為 \(1\)，因此費用是 \(F[u][v]\)。
• 若 \(u\ne v\) 且 \(F[u][v]\le1000\)，每單位流量費用為 \(3\)。
• 若 \(u\ne v\) 且 \(F[u][v]>1000\)，前 \(1000\) 單位每單位仍為 \(3\)， 只有超過 \(1000\) 的部分每單位為 \(2\)。此時費用為

一個方案的總費用，是所有城市對 \((u,v)\) 的費用總和。請找出 \(k\) 個方案 之中的最低總費用。

輸入格式

第一行包含三個整數 \(n,m,k\)。

接下來 \(n\) 行，每行包含 \(m\) 個整數。第 \(i\) 行的第 \(j\) 個整數是 \(Q[i][j]\)。

再接下來 \(k\) 行，每行包含 \(n\) 個整數 \(c_0,c_1,\ldots,c_{n-1}\)，表示一個配置方案。

限制

• \(1\le n,m,k\le50\)
• \(0\le Q[i][j]\le1000\)
• \(0\le c_i<m\)
• 所有輸入都是整數。

輸出格式

輸出一個整數，表示所有方案中的最低總費用。

評分說明

兩筆範例會由評測系統執行，但不計分。另有恰好 \(20\) 個計分測試組， 每組 \(5\) 分：

• 第 \(1\)～\(4\) 組（共 \(20\) 分）：\(n=1\) 且 \(k=1\)。
• 第 \(5\)～\(10\) 組（共 \(30\) 分）：\(n=1\)。
• 第 \(11\)～\(20\) 組（共 \(50\) 分）：沒有額外限制。

範例輸入 1

2 3 3
30 23 23
5 25 3
0 0
0 1
0 2

範例輸出 1

217

範例解釋 1

三個方案的總費用依序為 \(257\)、\(217\)、\(261\)，因此答案是 \(217\)。

以第二個方案 \((0,1)\) 為例，伺服器 \(0\) 在城市 \(0\)，伺服器 \(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

13470

題目來源

APCS 2021 年 1 月實作題第 2 題；規則參考 ZeroJudge f606「流量」 與王一哲的題解，題目敘述由 AACPOJ 重新整理。