a129 - 最小生成樹
題目描述
題目要求計算給定加權無向圖的最小生成樹 (MST) 的權重和。如果圖不連通，則輸出 -1。
解題思路
本題採用 Kruskal's Algorithm 求解最小生成樹。Kruskal's Algorithm 是一種貪心演算法，其步驟如下：
- 將所有邊按照權重從小到大排序。
- 初始化一個 Disjoint Set Union (DSU) 資料結構，每個頂點都屬於自己的集合。
- 遍歷排序後的邊，對於每一條邊 (u, v)：
- 如果 u 和 v 屬於不同的集合，則將它們合併到同一個集合，並將該邊的權重加到 MST 的權重和中。
- 如果 MST 包含 n-1 條邊（其中 n 是頂點數），則 MST 存在，輸出權重和。否則，圖不連通，輸出 -1。
Disjoint Set Union (DSU) 資料結構用於追蹤圖的連通性。它提供了兩個主要操作：
find(x): 找到包含頂點 x 的集合的代表元素。union(x, y): 將包含頂點 x 和 y 的集合合併。
複雜度分析
- 時間複雜度: O(E log E)，其中 E 是邊的數量。排序邊需要 O(E log E) 的時間，遍歷邊和執行 DSU 操作需要 O(E α(V)) 的時間，其中 V 是頂點的數量，α(V) 是反阿克曼函數，增長非常慢，可以視為常數。
- 空間複雜度: O(V + E)，其中 V 是頂點的數量，E 是邊的數量。需要 O(V) 的空間來儲存 DSU 資料結構，需要 O(E) 的空間來儲存邊。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,s[100001];
struct p{
int x,y,v;
};
p a[10000001];
bool cmp(p xx,p yy){
if(xx.v<yy.v||(xx.v==yy.v&&xx.y<yy.y)||(xx.v==yy.v&&xx.y==yy.y&&xx.x<yy.x))return 1;
return 0;
}
int fd(int xx){
if(s[xx]==xx)return xx;
return s[xx]=fd(s[xx]);
}
void un(int xx,int yy){
s[yy]=fd(s[xx]);
}
int main(){
cin.sync_with_stdio(false), cin.tie(0);
while(cin >> n >> m){
for(int i=0;i<n;++i){
s[i]=i;
}
for(int i=0;i<m;++i){
cin >> a[i].x >> a[i].y >> a[i].v;
}
sort(a,a+m,cmp);
long long int num=0,ans=0;
for(int i=0;i<m;++i){
//cout << a[i].x << " " << a[i].y << " " << a[i].v << "\n";
int fdx=fd(a[i].x),fdy=fd(a[i].y);
if(fdx!=fdy){
un(fdx,fdy);
++num;
ans+=a[i].v;
}
}
if(num==n-1){
cout << ans << '\n';
}
else{
cout << "-1\n";
}
}
}