P2052 [NOI2011] 道路修建

題目描述

在 W 星球上有 $n$ 個國家。為了各自國家的經濟發展，他們決定在各個國家之間建設雙向道路使得國家之間連通。但是每個國家的國王都很吝嗇，他們只愿意修建恰好 $n?1$ 條雙向道路。

每條道路的修建都要付出一定的費用，這個費用等于道路長度乘以道路兩端 的國家個數之差的絕對值。例如，在下圖中，虛線所示道路兩端分別有 $2$ 個、$4$ 個國家，如果該道路長度為 $1$，則費用為 $1\times |2?4|=2$。圖中圓圈里的數字表示國家的編號。

由于國家的數量十分龐大，道路的建造方案有很多種，同時每種方案的修建費用難以用人工計算，國王們決定找人設計一個軟件，對于給定的建造方案，計算出所需要的費用。請你幫助國王們設計一個這樣的軟件。

輸入格式

輸入的第一行包含一個整數 $n$，表示 W 星球上的國家的數量，國家從 $1$ 到 $n$ 編號。

接下來 $n?1$ 行描述道路建設情況，其中第 $i$ 行包含三個整數 $a_i$，$b_i$ 和 $c_i$，表示第 $i$ 條雙向道路修建在 $a_i$ 與 $b_i$ 兩個國家之間，長度為 $c_i$。

輸出格式

輸出一個整數，表示修建所有道路所需要的總費用。

輸入輸出樣例 #1

輸入 #1

6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1

輸出 #1

20

說明/提示

對于 $100\%$ 的數據，$1\le a_i,b_i\le n$，$0\le c_i\le 10^6$，$2\le n\le 10^6$。

測試點編號	$n=$
$1$	$2$
$2$	$10$
$3$	$100$
$4$	$200$
$5$	$500$
$6$	$600$
$7$	$800$
$8$	$1000$
$9$	$10^4$
$10$	$2\times 10^4$
$11$	$5\times 10^4$
$12$	$6\times 10^4$
$13$	$8\times 10^4$
$14$	$10^5$
$15$	$6\times 10^5$
$16$	$7\times 10^5$
$17$	$8\times 10^5$
$18$	$9\times 10^5$
$19,20$	$10^6$

solution

任以一個節點為根節點，dfs 統計每一個子樹 u 的 size 對于每條邊 e 的長度為 w, 則該邊的費用為 w * abs(n - 2 * size), 對所有邊費用求和即可

代碼

#include<iostream>
#include<algorithm>
#include "cstring"
#include "vector"using namespace std;/** P2052 [NOI2011] 道路修建* 題目大意: 一個有權無向連通圖，要得到一顆樹，使得費用最小，費用為樹的邊費用之和，邊的費用為邊的長度乘以邊兩端的節點數量之差。** 思路:*      任以一個節點為根節點，dfs 統計每一個子樹 u 的 size 對于每條邊 e 的長度為 l*      則該邊的費用為 l * abs(n - 2 * size), 求和即可**/typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 5;int n;
ll ans;
vector<pii> e[N];int dfs(int u, int p) {int siz = 1;for (auto [v, w]: e[u]) {if (v == p) continue;int siz_v = dfs(v, u);ans += 1ll * abs(n - 2 * siz_v) * w;siz += siz_v;}return siz;
}int main() {cin >> n;for (int i = 1, x, y, w; i < n; i++) {scanf("%d%d%d", &x, &y, &w);e[x].emplace_back(y, w);e[y].emplace_back(x, w);}dfs(1, 0);cout << ans << endl;return 0;
}

結果