POJ_3723 Conscription

問題
解法
蟻本を参考にした。
最小全域木を求めればいいみたい。
連結成分ごとにプリム法を行うというやりかたをした。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> P; //最小コスト、位置
const int INF = 1 << 30;
const int MAX_NM = 10000;
class E{
public:
	int to, cost;
	E(int t, int c){to = t; cost = c;}
};
vector<E> G[MAX_NM * 2];
int N, M, R;

int prim(){
	int ans = 0;
	bool used[N + M]; //Xに含まれているか
	fill(used, used + N + M, false);
	//連結成分ごとにプリム法を行う
	for(int k = 0; k < N + M; k++){
		if(used[k]) continue;
		priority_queue<P, vector<P>, greater<P> > Q;
		Q.push(P(0, k));
		while(!Q.empty()){
			int v, co;
			v = Q.top().second;
			co = Q.top().first; Q.pop();
			if(used[v]) continue;
			used[v] = true; //Xに追加
			ans += co;
			for(int i = 0; i < G[v].size(); i++){
				if(!used[G[v][i].to]) //まだ追加されていなければ
					Q.push(P(G[v][i].cost, G[v][i].to));
			}
		}
	}
	return ans;
}
int main(){
	int CASE;
	scanf("%d", &CASE);
	for(int c = 0; c < CASE; c++){
		for(int i = 0; i < MAX_NM * 2; i++){
			G[i].clear();
		}
		scanf("%d %d %d", &N, &M, &R);
		for(int i = 0; i < R; i++){
			int g, b, cost;
			scanf("%d %d %d", &g, &b, &cost);
			G[g].push_back(E(N + b, -cost));
			G[N + b].push_back(E(g, -cost));
		}
		int s = -prim();
		int ans = (M + N) * 10000 - s;
		printf("%d\n", ans);
	}
	return 0;
}