POJ 1258

一水，最小生成树，缓解心情

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=(1<<31)-1;
int map[110][110];
int lowest[110];
bool vis[110];

void init(int n){
	for(int i=1;i<=n;i++)
	lowest[i]=inf;
	memset(vis,false,sizeof(vis));
}

void slove(int n){
	lowest[1]=0;
	for(int i=2;i<=n;i++)
	lowest[i]=map[1][i];
	vis[1]=true;
	for(int i=1;i<=n;i++){
		int pos=-1,minc=inf;
		for(int k=1;k<=n;k++){
			if(!vis[k]&&minc>lowest[k]){
				minc=lowest[k]; pos=k;
			}
		}
	//	cout<<minc<<' '<<pos<<endl;
		if(pos==-1) break;
		vis[pos]=true;
		for(int k=1;k<=n;k++){
			if(!vis[k]){
				if(lowest[k]>map[pos][k])
				lowest[k]=map[pos][k];
			}
		}
	}
}

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
			scanf("%d",&map[i][j]);
		}
		init(n);
		slove(n);
		int ans=0;
		for(int i=1;i<=n;i++)
		ans+=lowest[i];
		printf("%d
",ans);
	}
	return 0;
}