題目連結: https://zerojudge.tw/ShowProblem?problemid=a129
# 內容
給你一個加權的無向圖 (weighted undirected graph)，請問這個圖的最小生成樹 (minimum spanning tree) 的權重和為多少？
# 解題思路
每次都從未加入的點中，加入權重最小的點，直到每個點都被加入。
如果加入的數量小於 n 代表不是所有皆連通
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
struct Tree | |
{ | |
int s,e,w; | |
}; | |
bool cmp(Tree a,Tree b) | |
{ | |
return a.w<b.w; | |
} | |
int p[100000]; | |
int Find(int a){ | |
if (p[a] == a) return a; | |
else { | |
p[a] = Find(p[a]); | |
return p[a]; | |
} | |
} | |
void Kruskal(int n,int m) | |
{ | |
Tree dot[m]; | |
for(int i=0;i<n;i++) | |
p[i]=i; | |
for (int i=0;i<m;i++) | |
cin >>dot[i].s>>dot[i].e>>dot[i].w; | |
sort(dot,dot+m,cmp); | |
ll ans=0,cnt = 0; | |
for (int i=0,x,y;i<m;i++) { | |
x = Find(dot[i].e); | |
y = Find(dot[i].s); | |
if(x==y) continue; | |
else { | |
p[y] = x; | |
ans +=dot[i].w; | |
cnt++; | |
} | |
} | |
if(cnt==n-1)cout<<ans; | |
else cout<<-1; | |
cout<<"\n"; | |
} | |
int main() { | |
int n,m; | |
while (cin >>n>>m) | |
Kruskal(n,m); | |
return 0; | |
} |
