//这道题要卡常数吗？
//大佬们请留步，谢谢
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 10000;
const int MAXE = 50000;
struct Edge
{
	int u;
	int v;
	int val;
};
struct Edge g[MAXE+2];
int fa[2*MAXN+2];
int n,m,e;
int ans;

void cases();
int find_fa(int);
void union_fa(int,int);
bool cmp(struct Edge,struct Edge);
int Kruskal();

int main()
{
	int t;
	
	scanf("%d",&t);
	
	while(t--)
	{
		cases();
	}
	
	return 0;
}

void cases()
{
	int i,x,y,z;
	
	scanf("%d%d%d",&n,&m,&e);
	for(i=0; i<e; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		g[i].u = x;
		g[i].v = y+n;
		g[i].val = z;
	}
	
	ans = Kruskal();
	ans = 10000*(n+m)-ans;
	
	printf("%d\n",ans);
}

int find_fa(int m)
{
    int i,j,k;
    i = m;

    while(fa[i] != i)
    {
        i = fa[i];
    }
    j = i;
    while(i != j)
    {
        i = fa[k];
        fa[k] = j;
        k = i;
    }
    return j;
}

void union_fa(int m,int n)
{
    int p,q;
    p = find_fa(n);
    q = find_fa(m);
    if(fa[p] != q)
    {
        fa[p] = q;
    }
}

bool cmp(struct Edge x,struct Edge y)
{
	return x.val>y.val;
}

void Kruskal_UFSreset()
{
	int i;
	
	for(i=0; i<=MAXN*2; i++)
	{
		fa[i] = i;
	}
}

int Kruskal()
{
	int i,ans,p,q;
	
	Kruskal_UFSreset();
	sort(g,g+e,cmp);
	
	ans = 0;
	for(i=0; i<e; i++)
	{
		p = find_fa(g[i].u);
		q = find_fa(g[i].v);
		if(p != q)
		{
			ans+=g[i].val;
			union_fa(p,q);
		}
	}
	
	return ans;
}

• Re:蒟蒻求助。。。TLE快要吐了。。。这道题要卡常数吗？ (94) 768059009 2017-06-17 18:43:42
• Re:蒟蒻求助。。。TLE快要吐了。。。这道题要卡常数吗？ (1777) 928532612 2017-06-26 23:12:22