题意
要征募n个男兵，m个女兵，每招一个人要10000块钱，现在有一些男兵和女兵有某种关系，导致同时招募他们可以节省一定的钱，给出男女兵的关系，求招募最少要花多少钱。
思路
其实很简单，选的人里面含有的关系能省的钱要最大，把男女关系连起来形成一个图，就是求这个图的最大生成树。我们猜测最大生成树算法可以类比最小生成树的贪心算法（确实是对的）。不过我们这里可以换个思路，把权值全改成负数，那这样求最小生成树得到的也是我们要的值。
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int kMaxn = 50000 + 10;struct Edge {int u,v;int d;
} g[kMaxn];int f[kMaxn];
int n,m,r;int Init() {for(int i = 0; i <= n + m; i++)f[i] = i;
}int Findf(int x) {if(f[x] != x)f[x] = Findf(f[x]);return f[x];
}void Union(int a, int b) {int fa = Findf(a);int fb = Findf(b);f[fb] = fa;
}bool cmp(Edge a, Edge b) {return a.d < b.d;
}int Kruskal() {Init();int sum = 0;sort(g + 1, g + 1 + r, cmp);for(int i = 1; i <= r; i++) {int u = g[i].u;int v = g[i].v;if(Findf(u) != Findf(v)) {sum += g[i].d;Union(u, v);}}return sum;
}int main() {int T;scanf("%d", &T);while(T--) {scanf("%d %d %d", &n, &m, &r);memset(g, 0, sizeof(g));for(int i = 1; i <= r; i++) {int u,v,d;scanf("%d %d %d", &u, &v, &d);g[i].u = u;g[i].v = v + n;g[i].d = -d;}printf("%d\n", (n + m) * 10000 + Kruskal());}return 0;
}