POJ(PKU) 1258 Agri-Net

解法：プリム法、またはクラスカル法をやるだけ。

なぜプリム法を選んだのかは自分でもわからん。気づいたら組んでいた。

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAX_V = 100;
const int INF = 100000000;

int cost[MAX_V][MAX_V];
int mincost[MAX_V];
bool used[MAX_V];
int V;

int prim(){
  for(int i = 0;i < V;i++){
    mincost[i] = INF;
    used[i] = false;
  }
  mincost[0] = 0;
  int res = 0;
  
  while(true){
    int v = -1;
    
    for(int u = 0;u < V;u++){
      if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
    }
    
    if(v == -1) break;
    used[v] = true;
    res += mincost[v];
    
    for(int u = 0;u < V;u++){
      mincost[u] = min(mincost[u], cost[v][u]);
    }
  }
  return res;
}

int main(){
  
  while(cin >> V){

    for(int i = 0;i < V;i++){
      for(int j = 0;j < V;j++){
	int t;
	scanf("%d",&t);
	cost[i][j] = t;
      }
    }
    
    printf("%d\n",prim());
  }
  return 0;
}