其实就是要求最小的环套树森林
我们现在只考虑如何合并 设当前边的两个端点是x,y
若x,y在一个联通块里
那这个联通块要么是树 要么是环套树
假如是个环套树 加一条边后必定变成两个环 不符合要求 假如是个树 加一条边就变成了换套树 符合要求
若x,y不在一个联通块里
假如同为环套树 加一条边后必定变成两个环 不符合要求 假如同为树 加一条边后还是树 符合要求 假如一棵树 一棵环套树 加了过后变成环套树 符合要求
然后类似kruskal就好了
#include<bits/stdc++.h> #define N 500005 #define int long long using namespace std; struct data { int x,y,z; }edge[2*N]; int father[N]; int n,m,tot,type[N]; //type=0 树 type=1 环 inline bool cmp(const data &a,const data &b) { return a.z<b.z; } inline void addedge(int x,int y,int z) { tot++; edge[tot].x=x,edge[tot].y=y,edge[tot].z=z; } inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } main() { cin>>n>>m; for(int i=1;i<=n;i++) father[i]=i; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } sort(edge+1,edge+tot+1,cmp); int ans=0,cnt=0; for(int i=1;i<=m;i++) { int fx=getfather(edge[i].x),fy=getfather(edge[i].y); if(fx==fy) //在一个联通块 { if(type[fx]==0)//是个树 { type[fx]=1; //他将变成环套树 ans+=edge[i].z; ++cnt; } //环肯定是不能再加边的 } else { if(type[fx]&&type[fy]) continue; //两个环 father[fx]=fy; type[fy]=type[fy]|type[fx]; ans+=edge[i].z; ++cnt; } } if(cnt!=n) puts("No"); else cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9798702.html
