#include<iostream>
using namespace std;
int n;
long dis[105][105];
long cost[105];
bool vis[105];
long long ans=0;
void prim()
{
	int k;
	for (int i=1; i<=n; i++)
	{
		long minn=2139062143;
		for (int j=1; j<=n; j++)
		{
		     if (!vis[j] && cost[j]<minn)
			 {
			 	minn=cost[j];
			 	k=j;
			 }	
		}
		vis[k]=true;
		ans+=minn;
		for (int j=1; j<=n; j++)
			if (!vis[j] && dis[k][j]>0 && dis[k][j]<cost[j])
			cost[j]=dis[k][j];
	}
}
void init()
{
	cin>>n;
	for (int i=1; i<=n; i++)
	   for (int j=1; j<=n; j++)
	     cin>>dis[i][j];
    for (int i=1; i<=n; i++)
    {
    	cost[i]=2139062143;
    	vis[i]=false;
    }
    cost[1]=0;
}
int main()
{
	init();
	prim();
	cout<<ans<<endl;
}

• Re:为什么这个过不了poj1258，不就是裸prim么 (17) Greetrix 2014-07-24 17:57:18