http://poj.org/problem?id=3723
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10000+10;
int father[N+N];
int grade[N+N];
struct Edge
{
int from,to,w;
bool operator <(const Edge& that) const
{
return w>that.w;
}
}arr[50010],tmp;
int parent(int v)
{
while(v!=father[v])
{
father[v]=father[father[v]];
v=father[v];
}
return v;
}
int connect(int a,int b)
{
int fa=parent(a);
int fb=parent(b);
if(fa==fb) return 0;
if(grade[fa]>grade[fb])
{
father[fb]=fa;
grade[fa]+=grade[fb];
}
else
{
father[fa]=fb;
grade[fb]+=grade[fa];
}
return 1;
}
int main()
{
int t,n,m,r,a,b,c;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&r);
for(int i=0;i<=n+m+1;i++)
{
father[i]=i;
grade[i]=1;
}
for(int i=0;i<r;i++)
{
scanf("%d%d%d",&arr[i].from,&arr[i].to,&arr[i].w);
arr[i].to+=n;
}
sort(arr,arr+r);
int ans=0;
for(int i=0;i<r;i++)
{
int a=arr[i].from,b=arr[i].to;
if(connect(a,b))
{
ans+=arr[i].w;
}
}
printf("%d\n",(n+m)*10000-ans);
}
}
