POJ 3723 Conscription

Description

对n个女生m个男生征兵，这些女生中部分与男生间有关系d，征一人入伍需10000，若一女生已被征，去征召跟她有关系d的男生只需花费10000-d，相反亦然。问征全部人最小花费

Idea

将女生标号（0~ n-1）偏移在男生（0 ~ m-1）之上: （m ~ m+n-1）构成图

其实关系值d代表应征一个人可以减少的花费，那么求一个最大生成树即最多减少的花费

10000 * （n + m） - 最大生成树 即最终的最少花费

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100005;

int n, m, r, ans;
int pre[N * 2];

int cnt;
struct edge
{
    int there, here, w;
} a[N * 2];

bool cmp(edge a, edge b)
{
    return a.w > b.w;
}

void init()
{
    ans = 0;
    for(int i = 0; i <= n + m; ++i)
        pre[i] = i;
}

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);
    return pre[x];
}

int unite(edge t)
{
    int x = found(t.there);
    int y = found(t.here);
    if(x != y)
    {
        pre[y] = x;
        return t.w;
    }
    return 0;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &r);
        init();
        int b, c, d;
        for(int i = 0; i < r; ++i)
        {
            scanf("%d%d%d", &a[i].there, &a[i].here, &a[i].w);
            a[i].there += m;
        }
        sort(a, a + r, cmp);
        for(int i = 0; i < r; ++i)
            ans += unite(a[i]);
        cout << 10000 * (n + m) - ans << '\n';
    }
    return 0;
}