aoj

ALDS1_12_A Minimum Spanning Tree

ALDS1_12_A Minimum Spanning Tree
Feb. 2, 2020, 1:52 p.m.

目次

解答

プリムのアルゴリズム

  1. 3つの配列を頂点数の長さで宣言する

    1. parent[n] ・・・頂点iがMST(最小全域木)に組み込まれた時の接続先頂点.隣接行列と参照して辺とそのコストがわかる。

    2. key[n] ・・・作成中MSTに次に組み込む可能性のある隣接頂点iへのコスト.

    3. mst[n] ・・・頂点がMSTに組み込まれているか否か.最終的にはすべての頂点が組み込まれる。

  2. 最初は頂点0から始めるために、key[0]を0に、その他はありえない最大値に初期化する
  3. MSTは空にする(mstをすべてfalseに)
  4. すべての頂点がMSTに含まれるまで以下を繰り返す(最後の頂点は1つで選択の余地がないので頂点数-1だけ実行)

    1. まだMSTに未追加の隣接頂点のうち、コストが最小であるものをuとし、MSTに加える.

    2. MSTに含まれずuに隣接するすべての頂点vのうち最小コストをkey[v]に格納しvの親をuとする.

  5. すべての辺のコストを隣接行列を参照して合計する.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define MAX_N 100
#define MAX_INT (1 << 21)


Int prim(Int W[MAX_N][MAX_N], Int n) {
  Int parent[n], key[n];
  bool mst[n];

  loop(i,0,n) key[i] = MAX_INT, mst[i] = false;

  key[0] = 0, parent[0] = -1;
  loop(count,0,n-1) {
    Int u, min_ = MAX_INT;
    loop(i,0,n) {
      if (!mst[i] && key[i] < min_) {
        min_ = key[i], u = i;
      }
    }

    mst[u] = true;

    loop(v,0,n) {
      if (!mst[v] && W[u][v] < key[v]) {
        key[v] = W[u][v], parent[v] = u;
      }
    }
  }

  Int sum_ = 0;
  loop(v,1,n) sum_ += W[v][parent[v]];
  return sum_;
}


int main(void) {
  Int W[MAX_N][MAX_N];
  Int n, w;
  cin >> n;

  loop(u,0,n) {
    loop(v,0,n) {
      cin >> w;
      W[u][v] = W[v][u] = (w == -1) ? MAX_INT : w;
    }
  }

  cout << prim(W, n) << endl;
}