#include <iostream>
#include <fstream>
using namespace std;

int n;
int mark[110];
int cost[110][110];

int total;


void prim(){
	mark[1]=1;
	int dest[110];
	int i,j,k;

	for(i=2;i<=n;i++){
		dest[i]=cost[1][i];
	}
	for(i=1;i<n;i++){
		int min=1000000;
		int node=-1;
		for(j=1;j<=n;j++){
			if(mark[j]==0&&dest[j]<min){
				min=dest[j];
				node=j;
			}
		}
		mark[node]=1;
		total+=min;
		for(j=1;j<=n;j++){
			if(mark[j]==0&&dest[j]>cost[node][j]){
				dest[j]=cost[node][j];
			}
		}

	}
}




void main(){
//	ifstream cin("data.txt");
	while(cin>>n){
		int i,j,k;

		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				cin>>cost[i][j];
			}
		}
		total=0;
		prim();
		cout<<total<<endl;

	}
}

• Re:这么简单的题目为什么给我WA？？难道我PRIM错了？？？ (866) bigyellow 2007-10-04 13:18:44
• 测了 n =3 再继续测n=4你就知道了 (866) bigyellow 2007-10-04 13:19:44