本文主要是介绍Pseudoforest HDU - 3367，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3367
一开始想当然地求最大生成树然后再加边 WA。。 看题解就是把克鲁斯卡尔的判连通再加上判环就好 这样还是符合原算法的贪心策略的
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=1e5+10;struct node
{int u,v,w;
};node pre[maxm];
int first[maxn],f[maxn],cnt[maxn];
int n,m,num;bool cmp(node n1,node n2)
{return n1.w>n2.w;
}int getf(int p)
{if(f[p]==p) return p;else return f[p]=getf(f[p]);
}int unite(int u,int v,int w)
{int fu,fv;fu=getf(u),fv=getf(v);if(fu!=fv){if(cnt[fu]+cnt[fv]<=1){f[fv]=fu;if(cnt[fu]+cnt[fv]==1) cnt[fu]=1;return w;}else return 0;}else if(cnt[fu]==0){cnt[fu]=1;return w;}else return 0;
}int main()
{int i,ans,fu;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;for(i=1;i<=m;i++){scanf("%d%d%d",&pre[i].u,&pre[i].v,&pre[i].w);pre[i].u++,pre[i].v++;}sort(pre+1,pre+m+1,cmp);for(i=1;i<=n;i++) f[i]=i,cnt[i]=0;ans=0;for(i=1;i<=m;i++) ans+=unite(pre[i].u,pre[i].v,pre[i].w);printf("%d\n",ans);}return 0;
}
这篇关于Pseudoforest HDU - 3367的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
