题目描述：

要招n女，m男，每招一个人需要10000元，但是有一些男女有关系，代价为d，比如第i个女和第j个男有代价为d的关系，那么他们任意一个如果已经被招，则招另一个只需10000 - d元，问最少要用多少元招完这n女m男。

解题报告：

最大生成树的方法把关系按照从大到小的顺序遍历一遍，对于每个关系，只要这个关系的两个一个被招，一个还没被招（用并查集实现），就省下d元，同时把两个人都更新为被招的状态。最后答案就是本来需要的钱（n + m) * 10000减去省下的钱即可。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
struct edge{int x, y, v;} e[50000];
bool cmp(edge a, edge b){return a.v > b.v;}
int f[20000], t, n, m, r, ans;
int find(int pos)
{
    if (f[pos] == -1) return pos;
    return f[pos] = find(f[pos]);
}
bool un(int a, int b)
{
    int fa = find(a), fb = find(b);
    if (fa == fb) return false;
    f[fa] = fb;return true;
}
void kruskal()
{
    sort(e, e + r, cmp);ans = 0;
    for(int i = 0; i < r; i++)
        if (un(e[i].x, n + e[i].y)) ans += e[i].v;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &r);
        memset(f, -1, sizeof(int) * (n + m));
        for(int i = 0; i < r; i++)
            scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].v);
        kruskal();
        printf("%d\n", (n + m) * 10000 - ans);
    }
    return 0;
}