思路:
1.先存储所有的边,包括起点,终点,权值u,v,w
2.对所有的边按权值从小到大排序
3.最小生成树得到的边数一定是n-1(点的数目减一),按权值从小到大取边,如果选中该边,就把这条边的两个点加入到一个集合(表示有同样的归属关系,就是我们所说的并查集)里面,下次选边时,如果有节点已经在这个集合中,说明会构成回路,不满足最小生成树的性质,就要抛弃这条边。
#include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int ,int> pii; const int inf = 0x3f3f3f3f; const int N = 2e5+5; int n,m,cnt,ans,f[N]; struct edge { int u,v,w; }e[200005]; int find(int x) { return f[x]==x ? x: (f[x] = find(f[x])); } bool cmp(edge a,edge b) { return a.w<b.w; } void kruskal() { for(int i=1;i<=n;i++) f[i] = i; sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++) { int a = find(e[i].u); int b = find(e[i].v); if(a==b) continue; ++cnt; f[b] = a; if(cnt==n-1) { ans = e[i].w; break; } } cout<<cnt<<" "<<ans<<'\n'; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; e[i].u = a,e[i].v = b,e[i].w = c; } kruskal(); return 0; }
我的博客:
https://blog.csdn.net/qq_50285142/article/details/116927656