poj3723 Conscription

又到了写文章骂自己SB的时候。。。

这题的题意是某个人要找N个女孩和M个男孩。每个人需要付10000RMB。不过女孩x和男孩y有关联。当关联的人被招去了。那么剩下的那个人就可以在以dRMB找到。现在问你最小的招聘代价是多少。。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
using namespace std;
const int N=220000;
int u[N],v[N],w[N],r[N],f[N];
int n,m,R;
int vis[N];
void init()
{
	for(int i=0;i<n+m;i++)
	f[i]=i;
	for(int i=0;i<R;i++)
	r[i]=i;
} 
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
bool cmp(int i,int j)
{
	return w[i]>w[j];
}
int kursal()
{
	init();
	sort(r,r+R,cmp);
	int ans=(n+m)*10000;
	for(int i=0;i<R;i++)
	{
		int e=r[i];
		int x=u[e];
		int y=v[e];
		int fx=find(x);
		int fy=find(y);
		if(fx!=fy)
		{
			f[fx]=fy;
			ans-=w[e];
		}
	}
return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
    	scanf("%d %d %d",&n,&m,&R);
    	for(int i=0;i<R;i++)
    	{
    		int x,y,z;
    		scanf("%d %d %d",&x,&y,&z);
    		u[i]=x;
    		v[i]=n+y;
    		w[i]=z;
    	}
      int ans=kursal();
	  printf("%d
",ans);
    }
}