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);
    }

}