h559. pC. 共享自行車 (bike) - 高中生程式解題系統

內容

完整題目:https://drive.google.com/file/d/1RSq17g00V-ygkC8x37iLhtNteoqLAwZg/view?usp=sharing

給你一個有 $n - 1$ 個邊 $n$ 點的簡單無向圖，其中每個節點都可互通。

首先每個邊有距離也就是邊權，接著告訴你每個點有幾輛腳踏車(點權)，總共的腳踏車數為 $n \times k$ ，你的目標是讓每個點的腳踏車數量一樣，你可以把 $a$ 輛腳踏車從一個點移到跟它相鄰的點(調度)，花費是 $a \times$ 距離。問最少花費多少?

限制:

$1 \leq n \leq 10^{5}$

$1 \leq k \leq 10$

點權總和 $= n \times k$

$1 \leq$ 邊權 $\leq 10^{3}$

$0 \leq$ 點權 $\leq 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

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 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

提示：

題目和測資來源:twpca

另外抱歉這裡沒有分subtasks。

如果題目有問題歡迎來信詢問!

標籤:

DP Tree dfs

出處:

TOI入營考 2022 [管理者： rickysucksatcode@gmail.com

r1cky (hehe) ]

編號	身分	題目	主題	人氣	發表日期
34837	mushroom.cs9 ... (mushroom)	h559		406	2023-04-19 22:25