デブンキー一家の大活躍

問題 パソコン甲子園2008 08

n 個の都市がり、それらが m 本の橋で繋がっています。各橋の維持費（コスト）が決められています。どの都市にでも行くことができるように橋を残しつつ、橋の維持費の合計が最小になるように、いくつかの橋を壊したときの、維持費の合計を求めて下さい。

解説

重み付きグラフの最小全域木を求める問題です。サンプルは Prim のアルゴリズムで解きました。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define REP(i, e) for ( int i = 0; i < e; i++ )
004 #define MAX 100
005 static const int INFTY = (1<<21);
006 int G[MAX][MAX], n;
007 
008 int prim(){
009     int P[MAX], D[MAX];
010     bool V[MAX];
011     REP(i, n) { D[i] = INFTY; V[i] = false;}
012     D[0] = 0;
013     P[0] = -1;
014     int cost = 0;
015     while(1){
016         int u;
017         int minv = INFTY;
018         REP(i, n)  if ( !V[i] && D[i] < minv ){
019             minv = D[i]; u = i;
020         }
021         if ( minv == INFTY ) break;
022         V[u] = true;
023         if ( P[u] != -1 ) cost += G[u][P[u]];
024         
025         REP(v, n){
026             if ( G[u][v] != INFTY && !V[v] ){
027                 if ( D[v] > G[u][v] ){
028                     P[v] = u;
029                     D[v] = G[u][v];
030                 }
031             }
032         }
033     }
034     return cost;
035 }
036 
037 int main(){
038     int m, s, t, c;
039     while( cin >> n >> m && n){
040         REP(i, n) REP(j, n) G[i][j] = INFTY;
041         for ( int i = 0; i < m; i++ ){
042             cin >> s >> t >> c;
043             G[s][t] = G[t][s] = c;
044         }
045         cout << prim() << endl;
046     }
047 }