【AOJ ALDS1_12】A: Graph II - Minimum Spanning Tree
問題
最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 最小全域木(Minimum Spanning Tree)を作ろう.
- 全域木は閉路を持たない木(でいいのだろうか)
- 最小全域木は, 辺のコストの和が最も小さくなる全域木のこと.
- 頂点数がであることから, プリムのアルゴリズムを利用してMSTを求める.
- プリム法は, 以下のようなアルゴリズムである.
- 任意の頂点rを選び, Tに追加する.
- MSTに属する頂点の集合をT, グラフGの頂点の集合をVとする.
- Tに属する頂点とV-Tに属する頂点を繋ぐ辺の中で, コストが一番小さいノードuを選びそれをMSTの辺とする.
- uをTに追加する.
- これをV=Tとなるまで(2)から(4)を繰り返す.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define ALL(v) v.begin(), v.end() #define pb push_back #define INF 1e9 #define N_MAX 100 using namespace std; // 隣接行列 int G[N_MAX][N_MAX]; // d[i] := 頂点iからMSTの集合Tまでの最短距離 int d[N_MAX]; // 確定したノード bool visited[N_MAX]; // 親ノード int p[N_MAX]; void init(){ rep(i, N_MAX){ d[i] = INF; visited[i] = false; p[i] = -1; } } int prim(int n){ init(); // 始点は0 d[0] = 0; while(true){ int u = -1; int _min = INF; // 最短距離で行けるノードuを確定 rep(i, n){ if(d[i] < _min && !visited[i]){ u = i; _min = d[i]; } } if(u == -1) break; visited[u] = true; // ノードuから行けるノードの最短距離を更新 rep(v, n){ if(G[u][v] != -1 && !visited[v] && G[u][v] < d[v]){ d[v] = G[u][v]; p[v] = u; } } } int sum = 0; rep(i, n){ if(visited[i]){ sum += G[i][p[i]]; } } return sum; } signed main(){ int n; cin >> n; rep(i, n){ rep(j, n){ cin >> G[i][j]; } } cout << prim(n) << endl; }
ところで確定したノード適当にvisitedにしちゃったんですけどこれvisitじゃ色々おかしい気がする.