POJ-3723 Conscription

​​题目传送门​​

题意：

需要征募男兵N人，女兵M人。每征募一个人需要花费10000美元。但是如果已经征募的人中有一些关系亲密的人，那么可以少花一点钱。题目中给你R个男女之间的亲密度关系，如果n号男和m号女有亲密度关系，那么只要现在招募到他们中的一个人，那么招募另外一个人的花费将变为10000-他们之间的亲密度。然后要求你求出招募到所有人的最小花费。

因为全部人不一定都连接在一起，也就是全部人连接起来不一定是一棵树，可能是森林，像下面的图一样。

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