デブンキー一家の大活躍
2008.09.15 13:46 パソコン甲子園 2008
問題 パソコン甲子園2008 08
n 個の都市がり、それらが m 本の橋で繋がっています。各橋の維持費(コスト)が決められています。どの都市にでも行くことができるように橋を残しつつ、橋の維持費の合計が最小になるように、いくつかの橋を壊したときの、維持費の合計を求めて下さい。
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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |