Conscription

​​Conscription​​

如果两个人之间有关系，且动用了这一段关系，那么我们就把这两个人连起来，很明显最后得到的肯定是一个无环图，而最后的答案就是​

​ans=(n+m)*10000-图中总的权值​

​，要使 ans 最小，那么就要使图中总的权值最大，那么只需要根据已知边求一个最大生成树即可。

代码：

// Created by CAD on 2020/1/19.
#include <iostream>
#include <algorithm>
#include <cstdio>
#define ll long long
using namespace std;

const int maxn=5e4+5;
struct edge{
    int u,v,w;
    bool operator <(edge &x)
    {
        return w>x.w;
    }
}e[maxn];
int f[maxn];
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
ll ans=0;
int main()
{
    int t;  cin>>t;
    while(t--)
    {
        ans=0;
        int n,m,r;  scanf("%d%d%d",&n,&m,&r);
        for(int i=1;i<=r;++i)
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),
            e[i].v+=n+1,e[i].u++;
        for(int i=1;i<=n+m;++i)
            f[i]=i;
        sort(e+1,e+r+1);
        for(int i=1;i<=r;++i)
        {
            int x=find(e[i].u),y=find(e[i].v);
            if(x!=y)    ans+=e[i].w,f[x]=y;
        }
        cout<<1ll*(n+m)*10000-ans<<'\n';
    }
    return 0;
}