alan23273850 的刷題筆記
a129: 最小生成樹
出處：https://zerojudge.tw/ShowProblem?problemid=a129
提交：https://zerojudge.tw/Submissions?problemid=a129&account=allllllan123456
問題：給定一張有 $n\in[1,100000]$ 個點以及 $m\in[0,200000]$ 條權重邊的圖，試問最小生成樹的權重和？如果整張圖不連通則輸出 -1。
解法：用經典的 Kruskal’s algorithm 找生成樹即可。這題令人玩味的地方在於判斷圖是否連通，根據本頁的解說，一張連通圖的生成樹的邊數量為點數量少一，那麼兩張連通圖以上的所有生成樹的邊數量總和就必須比點數量總和少 2 以上。啊，記得權重和要用 long long。
1#include <bits/stdc++.h>
2using namespace std;
3
4int p[100000], w[200000];
5
6int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
7
8int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
9 int n, m, x[200000], y[200000], id[200000];
10 while (cin >> n >> m) { long long ans = 0;
11 for (int i=0; i<n; i++) p[i] = i;
12 for (int i=0; i<m; i++) id[i] = i,
13 cin >> x[i] >> y[i] >> w[i];
14 sort(id, id+m, [](int a, int b) { return w[a] < w[b]; });
15 n--; // 還剩下 n-1 條邊可以用
16 for (int i=0; i<m && n; i++) {
17 int x2 = find(x[id[i]]), y2 = find(y[id[i]]);
18 if (x2 != y2)
19 p[x2] = y2, ans += w[id[i]], n--;
20 }
21 if (!n) cout << ans << '\n'; // n-1 條邊都用完代表整張圖連通
22 else cout << -1 << '\n'; // 邊沒用完則一定不連通
23 }
24 return 0;
25}