poj - 1258
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f;
int mapp[1005][1005];
int n;
int sum;
int lowcast[1005];
int nearvex[1005];
void prim()
{
sum=0;
for(int i=1;i<=n;i++)
{
lowcast[i]=mapp[1][i];
nearvex[i]=1;
}
nearvex[1]=-1;
for(int i=1;i<n;i++)
{ int min=INF;
int v=-1;
for(int j=1;j<=n;j++)
{
if(nearvex[j]!=-1&&min>lowcast[j])
{
min=lowcast[j];
v=j;
}
}
nearvex[v]=-1;
sum=sum+lowcast[v];
// printf("sum=%d\n",sum);
for(int j=1;j<=n;j++)
{
if(nearvex[j]!=-1&&mapp[v][j]<lowcast[j])
{
lowcast[j]=mapp[v][j];
nearvex[j]=v; //还行没用。。。。
}
}
}
printf("%d\n",sum);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
{
scanf("%d",&mapp[i][j]);
}
}
}
prim();
}
}
