POJ_1258 Agri-Net
問題
解法
最小全域木をつくればいいからプリム法かクラスカル法をつかうといい
僕はプリム法を使いました。
#include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100; const int INF = 1 << 30; typedef pair<int, int> P; //(cost, v) int N; int G[MAX_N][MAX_N]; void solve(){ int ans = 0; bool X[N]; priority_queue<P, vector<P>, greater<P> > Q; fill(X, X + N, false); X[0] = true; for(int i = 1; i < N; i++) Q.push(P(G[0][i], i)); while(!Q.empty()){ P p = Q.top(); Q.pop(); int cost = p.first, v = p.second; if(X[v]) continue; ans += cost; X[v] = true; for(int u = 0; u < N; u++){ if(X[u]) continue; Q.push(P(G[v][u], u)); } } printf("%d\n", ans); return; } int main(){ while(scanf("%d", &N) != EOF){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ scanf("%d", &G[i][j]); } } solve(); } return 0; }