pku 1258 Agri-Net(标准prim)

这是O(v^2)的实现，以后就拿这个当模板了。

#include <iostream>

using namespace std;

int map[100][100];//存储边权值

bool inTree[100];

int min_length[100];//非Tree结点和Tree中的结点间的min_distance

int prim(int n)

{

int sum_length=0;

memset(inTree,0,sizeof(inTree));

for(int i=0;i<n;i++)//一开始，所有节点都是非Tree结点

{

min_length[i]=INT_MAX;

}

min_length[0]=0;//结点0作为起始结点

for(int i=0;i<n;i++)

{

int min_index=-1;

for(int j=0;j<n;j++)

{

if(!inTree[j]&&(min_index==-1||min_length[j]<min_length[min_index]))

min_index=j;

}

inTree[min_index]=true;//将新寻找到的结点加到tree中，标记

sum_length+=min_length[min_index];

for(int j=0;j<n;j++)//将所有和min_index相连的非tree结点的min_distance更新

{

if(!inTree[j]&&map[min_index][j]<min_length[j])

min_length[j]=map[min_index][j];

}

}

return sum_length;

}

int main()

{

int n;

while(scanf("%d",&n)!=EOF)

{

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

scanf("%d",&map[i][j]);

}

}

printf("%d/n",prim(n));

}

return 0;

}