POJ3723 Conscription

PS: 分析这是一道不错的题目，要求去抽象。

直接说结论： 题目可能是许森林，每一个森林有一颗最小生成树并且选择第一个点花费为10000。

这道题目实现的时候我对0 ~ M进行了编码为 N 到 M+N-1。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 20010;

struct edge {
    int from, to, w;
};

vector<edge> edges;
int f[MAXN];
int N, M, R;
bool cmp(edge x, edge y) {
    if(x.w != y.w) return x.w < y.w;
    else return false;
}

int getFather(int x) {
    if(f[x] == x) return x;
    else return f[x] = getFather(f[x]);
}

int work() {
    const int bound = N+M;
    for(int i = 0; i < bound; i++) f[i] = i;
    sort(edges.begin(), edges.end(), cmp);
    long long tot = 0;
    for(int i = 0; i < (int)edges.size(); i++) {
        edge &t = edges[i];
        int f1 = getFather(t.from);
        int f2 = getFather(t.to);
        if(f1 != f2) {
            f[f1] = f2;
            tot += t.w;
        }
    }
    int cnt = 0;
    for(int i = 0; i < bound; i++) {
        if(f[i] == i) cnt++;
    }
    return 10000*cnt + tot;
}


int main()
{
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &N, &M, &R);
        edges.clear();
        int x, y, w;
        edge t;
        for(int i = 1; i <= R; i++) {
            scanf("%d%d%d", &x, &y, &w);
            w = 10000-w;
            y = y + N; // encoding.
            t.from = x;
            t.to = y;
            t.w = w;
            edges.push_back(t);
        }
        int res = work();
        printf("%d\n", res);
    }
    return 0;
}

POJ3723 Conscription,布布扣,bubuko.com

POJ3723 Conscription

原文：http://blog.csdn.net/achiberx/article/details/28422515