日々精進

aikoと旅行とプログラミング

【AOJ ALDS1_12】A: Graph II - Minimum Spanning Tree

問題

最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge

方針

  • 最小全域木(Minimum Spanning Tree)を作ろう.
  • 全域木は閉路を持たない木(でいいのだろうか)
  • 最小全域木は, 辺のコストの和が最も小さくなる全域木のこと.
  • 頂点数が {0 \leq n \leq 100}であることから, プリムのアルゴリズムを利用してMSTを求める.
  • プリム法は, 以下のようなアルゴリズムである.
    1. 任意の頂点rを選び, Tに追加する.
    2. MSTに属する頂点の集合をT, グラフGの頂点の集合をVとする.
    3. Tに属する頂点とV-Tに属する頂点を繋ぐ辺の中で, コストが一番小さいノードuを選びそれをMSTの辺とする.
    4. uをTに追加する.
    5. これを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じゃ色々おかしい気がする.