POJ 3723 Conscription MST

http://poj.org/problem?id=3723

题目大意：

需要征募女兵N人，男兵M人，没征募一个人需要花费10000美元，但是如果已经征募的人中有一些关系亲密的人，那么可以少花一些钱，给出若干男女之间的1~9999之间的亲密度关系，征募某个人的费用是10000-（已经征募的人中和自己的亲密度的最大值），要求通过适当的征募顺序使得征募所有人的花费最小。

思路：

好几天没刷题，来水一发

征募了某个人a时，如果使用了a和b之间的关系，那么就连一条从a到b的边。那么根据贪心算法，每次选择最大的边，那么最后减去的花费就最多，也就是求最大生成树。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int cost=10000;

const int MAXN=20000+10;

const int MAXM=50000+10;

int n,m,r,fa[MAXN];

struct edge

{

	int from,to,val;

}e[MAXM];

bool operator <(const edge& a,const edge &b)

{

	return a.val>b.val;

}

int find(int cur)

{

	return cur==fa[cur]? cur:fa[cur]=find(fa[cur]);

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&n,&m,&r);

		for(int i=0;i<r;i++)

		{

			scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);

			e[i].to+=n;

		}

		for(int i=0;i<=n+m;i++)

			fa[i]=i;

		sort(e,e+r);

		int sum=0;

		for(int i=0;i<r;i++)

		{

			int x=e[i].from,y=e[i].to;

			int root_x=find(x),root_y=find(y);

			if(root_x==root_y) continue;

			fa[root_x]=root_y;

			sum+=e[i].val;

		}

		printf("%d\n",(n+m)*cost-sum);

	}

	return 0;

}