最小全域木

問題

実行時間制限: 1 sec/ メモリ制限: 65536 KB
与えられた重み付きグラフ \(G=(V,E)\) に対する最小全域木の辺の重みの総和を計算するプログラムを作成せよ。

入力

  • 最初の行に \(G\) の頂点数 \(n\) が与えられる。続く \(n\) 行で \(G\) を表す \(n×n\) の隣接行列 \(A\) が与えらえる。 \(A\) の要素 \(a_{ij}\) は頂点 \(i\) と頂点 \(j\) を結ぶ辺の重みを表す。ただし、辺がない場合は \(-1\) となる。

出力

  • \(G\) の最小全域木の辺の重みの総和を \(1\) 行に出力せよ。

制約

  • \(1 \leqq n \leqq 100\)
  • \(0 \leqq a_{ij} \leqq 2000\hspace{8px}(a_{ij}≠ -1のとき)\)
  • \(a_{ij} = a_{ji}\)
  • グラフ \(G\) は連結である。

例1

入力

\(5\)
\(-1 \hspace{8px} 2 \hspace{8px} 3 \hspace{8px} 1 \hspace{8px} -1\)
\(2 \hspace{8px} -1 \hspace{8px} -1 \hspace{8px} 4 \hspace{8px} -1\)
\(3 \hspace{8px} -1 \hspace{8px} -1 \hspace{8px} 1 \hspace{8px} 1\)
\(1 \hspace{8px} 4 \hspace{8px} 1 \hspace{8px} -1 \hspace{8px} 3\)
\(-1 \hspace{8px} -1 \hspace{8px} 1 \hspace{8px} 3 \hspace{8px} -1\)

出力

\(5\)

【出典・参考】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 296〜301頁
AIZU ONLINE JUDGE ADLS1_12_A https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/12/ALDS1_12_A

解答例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {

  int n;
  cin >> n;

  int INF = 0 - 10000;
  int graph[n][n];
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      int v;
      cin >> v;
      if (v == -1) {
        graph[i][j] = INF;
      } else {
        graph[i][j] = v;
      }
    }
  }

  int answer = 0;

  vector<bool> visited(n);
  vector<int> cost(n);

  // 頂点0は訪問済みにする
  visited[0] = true;

  // 各頂点の重みを頂点0からの重みとしておく
  for (int i = 0; i < n; i++) {
    cost[i] = graph[0][i];
  }

  while (1) {

    // 初期化
    int v = -1;

    for (int i = 0; i < n; i++) {

      // 訪問済みまたはコストがない=つながっていない場合は次の頂点へ
      if (visited[i] || cost[i] < 0) {
        continue;
      }

      // 重みが小さい頂点を探す
      if (v < 0 || cost[i] < cost[v]) {
        v = i;
      }

    }

    // 頂点が無い場合は終わり
    if (v < 0) {
      break;
    }

    // 見つかった頂点は訪問済みに
    visited[v] = true;

    // コストを加える
    answer += cost[v];

    // 繋がっている頂点のうち最小の重みを探す
    for (int i = 0; i < n; i++) {
      if (graph[v][i] < 0) {
        continue;
      }
      if (cost[i] < 0 || graph[v][i] < cost[i]) {
        cost[i] = graph[v][i];
      }
    }
  }

  cout << answer << endl;

  return 0;
}