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