题目链接<-点击
必须带一个环的最大生成树 模拟+最大生成树 思路： 1.当两个点不在同一棵树上时，若两个点都没有形成环，可以bing（）； 若其中一个有环另一个没有环，也可以bing（） 2.如果两个点在一棵树上，这两个点都必须没有环才可以bing(）； 代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=1000000; int pre[maxn],vis[maxn]; struct node { int l,r,val; }road[maxn]; int cmp(node aa,node bb) { return aa.val>bb.val; } int n,m; int findd(int x) { int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(i!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } void zyz() { for(int i=0;i<=n;i++) pre[i]=i,vis[i]=0; sort(road+1,road+1+m,cmp); int ans=0; //printf("0000000"); for(int i=1;i<=m;i++) { int tx=findd(road[i].l); int ty=findd(road[i].r); if(tx!=ty) { if(!vis[tx]&&!vis[ty]) { ans+=road[i].val; pre[ty]=tx; } else if(!vis[tx]&&vis[ty]) { vis[tx]=1; vis[ty]=1; pre[ty]=tx; ans+=road[i].val; } else if(!vis[ty]&&vis[tx]) { vis[tx]=1; vis[ty]=1; pre[ty]=tx; ans+=road[i].val; } } else { if(!vis[tx]&&!vis[ty]) { ans+=road[i].val; vis[findd(tx)]=1; //vis[tx]=1; //vis[ty]=1; } } } printf("%d\n",ans); } int main () { while(~scanf("%d%d",&n,&m)) { int i; if(n==0&&m==0) break; for(i=1;i<=m;i++) { scanf("%d%d%d",&road[i].l,&road[i].r,&road[i].val); } zyz(); } }