h559.
pC. 共享自行車 (bike)
內容
完整題目:https://drive.google.com/file/d/1RSq17g00V-ygkC8x37iLhtNteoqLAwZg/view?usp=sharing
給你一個有 $n-1$ 個邊 $n$ 點的簡單無向圖，其中每個節點都可互通。
首先每個邊有距離也就是邊權，接著告訴你每個點有幾輛腳踏車(點權)，總共的腳踏車數為 $n \times k$，你的目標是讓每個點的腳踏車數量一樣，你可以把 $a$ 輛腳踏車從一個點移到跟它相鄰的點(調度)，花費是 $a \times$ 距離。問最少花費多少?
限制:
$1 ≤ n ≤ 10^5$
$1 ≤ k ≤ 10$
點權總和 $=n \times k$
$1 ≤$ 邊權 $≤ 10^3$
$0 ≤$ 點權 $≤ n \times k$
輸入說明
首先第一行有兩個數 $n, k$。
接著一行有 $n$ 個數，分別代表目前點權，也就是一開始各點的腳踏車數量。
最後有$n-1$行，每行三個數 $u$ 、 $v$ 、 $w$ ，代表有一個權重為 $w$ 且連接 $u$、$v$ 的雙向邊。
輸出說明
輸出最小花費成本。
範例輸入
#1
8 2 4 2 2 1 3 3 0 1 1 2 3 2 3 1 3 4 2 5 6 2 6 7 3 6 8 1 2 6 3
範例輸出
#1
21
範例輸入
#2
4 3 1 10 0 1 1 4 3 3 2 2 4 2 1
範例輸出
#2
16
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <10M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <10M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
題目和測資來源:twpca
另外抱歉這裡沒有分subtasks。
如果題目有問題歡迎來信詢問!
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 34837 | mushroom.cs9 ... (mushroom) | h559 | 219 | 2023-04-19 22:25 |