#include<iostream>
using namespace std;
#define MAXN 102
#define  INF 0x3fffffff
int N,matrix[MAXN][MAXN],Low[MAXN];
int Prim()
{
	for(int i=2;i<=N;++i)Low[i]=matrix[i][1];
	int sum=0;
	for(int i=2;i<=N;++i)
	{
		int MIN=INF,p;
		for(int j=2;j<=N;++j)
		{
			if(Low[j]<MIN && Low[j])
			{
				p=j;
				MIN=Low[j];
			}
		}
		sum+=Low[p];
		Low[p]=0;
		for(int j=1;j<=N;++j)
		{
			if(matrix[j][p]<Low[j])
			{
				Low[j]=matrix[j][p];
			}
		}
	}
	return sum;
}
int main()
{
	while(cin>>N)
	{
		for(int i=1;i<=N;++i)
			for(int j=1;j<=N;++j)
				cin>>matrix[i][j];
		cout<<Prim()<<endl;
	}
	return 0;
}

• Re:第二次写Prim (2) Saleed 2016-11-02 21:22:50