PKU 1258-Agri-Net

問題概要

グラフの隣接行列表現が与えられる．最小全域木を作るのに必要なコストを求めろ．

解法

プリム法

実装(C++)

#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef vector<vector<int> > Matrix;
#define REP(i,x)for(int i=0;i<x;i++)
int prim(const Matrix &G){
	int V=G.size();
	vector<int> d(V,99999999);
	vector<bool> used(V,false);
	int ans=0;
	d[0]=0;
	REP(i,V){
		int m=99999999,n=-1;
		REP(j,V)
			if(!used[j]&&m>d[j])
				m=d[j],n=j;
		if(n==-1)return -1; //非連結
		used[n]=true;
		ans+=d[n];
		REP(j,V)
			d[j]=min(d[j],G[n][j]);
	}
	return ans;
}
int main() {
	int V;
	for(;~scanf("%d",&V);){
		Matrix G(V,vector<int>(V));
		for(int i=0;i<V;i++){
			for(int j=0;j<V;j++){
				scanf("%d",&G[i][j]);
			}
		}
		printf("%d\n",prim(G));
	}
	return 0;
}