tags: APCS

f606-流量

題目連結: 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,分別表示伺服器的數量、城市的數量和方案的數量。
  1. 讀取流量矩陣Q
Q = []
for i in range(n):
    row = list(map(int, input().split()))
    Q.append(row)
  • 這段程式碼從輸入中讀取n行,每行包含m個整數,存儲在二維列表Q中。這表示每個伺服器到每個城市的流量。
  1. 初始化花費列表
cost = [0 for i in range(k)]
  • 這行程式碼初始化一個列表cost,用來存儲每個方案的總花費,初始值全部設為 0。
  1. 計算每個方案的花費
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 塊錢。
  1. 找出最小花費並輸出
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)