(UnionFind・クラスカル法)POJ-3723-Conscription

問題URL→http://poj.org/problem?id=3723

蟻本の問題。
UnionFindのライブラリを整備してなかったのでちょうど良かった。
最小全域木アルゴリズムのクラスカル法もライブラリになかったので、これですぐ使えるようになった。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

//#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//UnionFind!!!
const int MAX_N = 30303;
int par[MAX_N];     //親
int myRank[MAX_N];  //木の深さ

//n要素で初期化
void init(int n)
{
    REP(i,n) {
        par[i] = i;
        myRank[i] = 0;
    }
}

//木の根を求める
int find(int x)
{
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
}

//xとyの属する集合を併合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (myRank[x] < myRank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (myRank[x] == myRank[y]) myRank[x]++;
    }
}

//xとyが同じ集合に属するか否か
bool same(int x, int y)
{
    return find(x) == find(y);
}

//クラスカル法!!!
struct edge
{
    int u, v, cost;
    edge() {}
    edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
};

bool comp(const edge& e1, const edge& e2)
{
    return e1.cost < e2.cost;
}

const int MAX_E = 50505;
edge es[MAX_E];
int V, E;

int kruskal()
{
    sort(es, es + E, comp);
    init(V);
    int res = 0;
    REP(i,E) {
        edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int caseNum;
int N, M, R;
int x, y, d;

signed main()
{
    cin >> caseNum;
    REP(i,caseNum) {
        cin >> N >> M >> R;
        V = N + M;
        E = R;
        REP(i,R) {
            //cin >> x >> y >> d;
            scanf("%d%d%d", &x, &y, &d);
            es[i] = edge(x, N + y, -d);
        }
        cout << 10000 * (N + M) + kruskal() << endl;
    }
}