本文主要是介绍poj 3723 Conscription （并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1 首先我们应该区分开男孩和女孩，只要将男孩的编号加上女孩的个数n，这样就可以做到男孩和女孩的编号是不同的。2 题目中说了如果两个人有关系，并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题，那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面，每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最小生成树相加，然后在加上s*10000（没有关系的时候选择一个人要10000），即为最后的答案。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define max 50005
using namespace std;
int pre[20010],n,m,r,ans;
struct edge
{int u,v,w;
}e[max];
int find(int x)
{int r=x;while(pre[r]!=r)r=pre[r];int i,j=x;while(j!=r){i=pre[j];pre[j]=r;j=i;}return r;
}
bool cmp(struct edge a,struct edge b)
{return a.w<b.w;
}
int dkstl()
{for(int i=0;i<m+n;++i)pre[i]=i;int x,y;sort(e,e+r,cmp);for(int i=0;i<r;++i){x=find(e[i].u);y=find(e[i].v);if(x!=y){ans+=e[i].w;pre[x]=y;}}/* sort(pre,pre+2*n);//waint ant=1;for(int i=1;i<2*n;++i){if(pre[i]!=pre[i-1])ant++;}*/int d[20010],ant=0;memset(d,0,sizeof(d));for(int i=0;i<n+m;++i){x=find(i);if(!d[x]){ant++;d[x]=1;}}cout<<10000*ant+ans<<endl;return 0;
}
int main()
{int t;cin>>t;while(t--){int u,v,w;cin>>n>>m>>r;for(int i=0;i<r;++i){scanf("%d %d %d",&u,&v,&w);e[i].u=u;e[i].v=v+n;e[i].w=10000-w;}ans=0;dkstl();}return 0;
}这篇关于poj 3723 Conscription （并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
