题目传送门
题意：
需要征募男兵N人，女兵M人。每征募一个人需要花费10000美元。但是如果已经征募的人中有一些关系亲密的人，那么可以少花一点钱。题目中给你R个男女之间的亲密度关系，如果n号男和m号女有亲密度关系，那么只要现在招募到他们中的一个人，那么招募另外一个人的花费将变为10000-他们之间的亲密度。然后要求你求出招募到所有人的最小花费。
因为全部人不一定都连接在一起，也就是全部人连接起来不一定是一棵树，可能是森林，像下面的图一样。
所以题目就是求这个森林的最大权，用最小生成树kruskal算法可求，最小值怎么变成最大值？正权边取反变成负权边，用负权边求最小值，再加绝对值不就是最大值吗?所以建图很明确了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MEM(a,x) memset(a,x,sizeof(a))
const int maxn=4*1e4+10;
struct Edge{
int from,to,len;bool operator<(const Edge &a)const{
return a.len>len;}
}edge[10*maxn];
int pre[maxn],Rank[maxn];
int n,m,r,tot,cnt;
void init()
{
tot=cnt=0;MEM(Rank,0);for(int i=1;i<=n+m;i++)pre[i]=i;
}
void Add(int from,int to,int len)
{
edge[tot].from=from;edge[tot].to=to;edge[tot++].len=len;edge[tot].from=to;edge[tot].to=from;edge[tot++].len=len;
}
int Find(int x)
{
if(x!=pre[x])pre[x]=Find(pre[x]);return pre[x];
} void unite(int x,int y)
{
int fx=Find(x);int fy=Find(y);if(Rank[fx]>Rank[fy])pre[fy]=fx;else{
pre[fx]=fy;if(Rank[fx]==Rank[fy])Rank[fy]++;}
}
int kruskal()
{
int Mintree=0;sort(edge,edge+tot);for(int i=0;i<tot;i++){
Edge e=edge[i];int u=e.from;int v=e.to;if(Find(u)!=Find(v)){
unite(u,v);Mintree+=e.len;}}return Mintree;
}
int main()
{
int T;scanf("%d",&T);while(T--){
scanf("%d%d%d",&n,&m,&r);init();for(int i=0;i<r;i++){
int u,v,len;scanf("%d%d%d",&u,&v,&len);u++;v++;Add(u,n+v,-len);}printf("%d\n",10000*(n+m)+kruskal());}
}