###### tags: `APCS`
# **f606－流量**
### **題目連結：** [**f606**](https://zerojudge.tw/ShowProblem?problemid=f606)
### **題目解析**
有 \( n \) 個伺服器編號從 0 到 \( n-1 \)，以及 \( m \) 個城市編號從 0 到 \( m-1 \)。每個伺服器需要傳送資料到各城市，已知每個伺服器 \( i \) 傳送到城市 \( j \) 的流量為 \( Q[i][j] \)。

工程師正在規劃將伺服器搬遷到城市中，對於一個方案 \( c = (c_1, c_2, ..., c_n) \)，表示編號 \( i \) 的伺服器要放在城市 \( c_i \)。

城市之間資料傳輸是需要費用的。若城市 \( u \) 要傳送資料到城市 \( v \)，費用的計算法如下：
- 若 \( u = v \)，單位流量需要 1 塊錢。
- 若 \( u != v \)，小於等於 1000 的流量每單位 3 塊錢，大於 1000 的部分每單位 2 塊錢。

若某伺服器有多個城市需要傳送資料到城市 \( u \)，會先將這些總量相加再計算費用。

工程師們總共提出了 \( k \) 種方案，請你找出花費最少的方案所需的費用。
### **解題方向**
1. 解析輸入資料，讀取伺服器數量 \( n \)、城市數量 \( m \)、方案數量 \( k \) 以及每個伺服器對每個城市的流量矩陣 \( Q \)。
2. 建立並初始化花費列表 \( cost \)。
3. 對每個方案計算伺服器配置的流量矩陣 \( flow \)。
4. 根據流量計算每個方案的總費用。
5. 找出最小費用並輸出。

### **程式解析**
1. 輸入與初始化

n, m, k = map(int, input().split())

* 這行程式碼從輸入中讀取三個整數n、m、k，分別表示伺服器的數量、城市的數量和方案的數量。

2. 讀取流量矩陣Q

Q = []
for i in range(n):
    row = list(map(int, input().split()))
    Q.append(row)

* 這段程式碼從輸入中讀取n行，每行包含m個整數，存儲在二維列表Q中。這表示每個伺服器到每個城市的流量。

3. 初始化花費列表

cost = [0 for i in range(k)]

* 這行程式碼初始化一個列表cost，用來存儲每個方案的總花費，初始值全部設為 0。

4. 計算每個方案的花費

for i in range(k):
    c = list(map(int, input().split()))  # 讀取一個方案
    flow = [[0 for x in range(m)] for y in range(m)]  # 初始化流量矩陣

    # 計算流量
    for x in range(n):
        for y in range(m):
            flow[c[x]][y] += Q[x][y]

    # 計算花費
    for x in range(m):
        for y in range(m):
            if x == y:
                cost[i] += flow[x][y]
            else:
                if flow[x][y] <= 1000:
                    cost[i] += flow[x][y] * 3
                else:
                    cost[i] += 1000 * 3
                    cost[i] += (flow[x][y] - 1000) * 2

* 這段程式碼對每個方案進行以下步驟：
* 讀取一個方案c，表示每個伺服器的位置。
* 初始化一個新的流量矩陣flow，用來存儲每個城市到其他城市的總流量。
* 遍歷每個伺服器x到每個城市y的流量，將其加到flow 矩陣中對應的位置。
* 根據流量矩陣flow 計算每個城市間的傳輸費用並累加到總花費中：
* 若伺服器與城市相同，則每單位流量費用為 1。
* 若伺服器與城市不同，根據流量大小計算費用，小於等於 1000 的部分每單位 3 塊錢，大於 1000 的部分每單位 2 塊錢。

5. 找出最小花費並輸出

min_cost = min(cost)
print(min_cost)

* 這段程式碼找出所有方案中花費最小的方案，並輸出最小花費。

### **完整程式碼**

def show_flow(arr, R, C):
    for i in range(R):
        for j in range(C):
            print(arr[i][j], end=' ')

        print()

# -------------------------------------

# 儲存 n, m, k
#start
n, m, k = map(int, input().split())
# n -> Server數量
# m -> City數量
# k -> 方案數量

# 儲存Q
Q=[]
for i in range(n): # 畫出一個二維陣列（表格）
    row = list(map(int, input().split()))
    Q.append(row)

# 初始化 cost(花費), 依據 k 種方案的結果
cost = [ 0 for i in range(k) ]

# 儲存 k 種方案 => 讀入一種方案 => 得到總金額 => next
for i in range(k):
    c=list(map(int,input().split())) # 有c1~cn

    # sever數量 n=m, n<m, n>m
    flow=[[0 for x in range(m)] for y in range(m)]

    # 流量有可能會需要重複計算, 加總流量
    for x in range(n):
        for y in range(m):
            flow[c[x]][y] += Q[x][y]

    #show_flow(flow, m, m)


    # 計算 cost (真正的花費)
    for x in range(m):
        for y in range(m):
            
            # 伺服器與城鎮相同
            if x == y:
                cost[i] += flow[x][y]

            else:
                
                if flow[x][y] <= 1000:
                    cost[i] += flow[x][y]*3
                
                else:
                    cost[i] += 1000*3
                    cost[i] += (flow[x][y]-1000)*2
    
    #print(cost[i])
min_cost = min(cost)
print(min_cost)