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; }