POJ 3723 Conscription

詳しくは蟻本p99参照

クラスカルやるだけ。

unionfindとkruskalなんも見ないで実装できたのでgood.

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_N = 20003;
const int MAX_E = 50003;

int par[MAX_N];
int rank[MAX_N];
struct edge{int from,to,cost;};
int V,E;
edge es[MAX_E];

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

void init(int n){
    for(int i = 0;i < n;i++){
	par[i] = i;
	rank[i] = 0;
    }
}

int find(int x){
    if(par[x] == x)return x;
    else{
	return par[x] = find(par[x]);
    }
}

void unite(int x,int y){
    x = find(x);
    y = find(y);

    if(x == y)return;

    if(rank[x] > rank[y]){
	par[y] = x;
    }else{
	par[x] = y;
	if(par[x] == par[y])rank[y]++;
    }
}

bool same(int x,int y){
    return (find(x) == find(y));
}


int kruskal(){

    init(V);
    sort(es,es + E,comp);

    int res = 0;

    for(int i = 0;i < E;i++){
	edge e = es[i];
	if(!same(e.from,e.to)){
	    res += e.cost;
	    unite(e.from,e.to);
	}
    }
    return res;
}

int main(){

    int t;
    scanf("%d",&t);

    while(t--){
	int n,m,r;
	scanf("%d%d%d",&n,&m,&r);

	V = n + m;
	E = r;

	for(int i = 0;i < r;i++){
	    int x,y,d;
	    scanf("%d%d%d",&x,&y,&d);
	    es[i] =(edge) {x,y+n,-d};
	}

	printf("%d\n",V*10000+kruskal());
    }
    return 0;
}