学步园

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

#include <iostream><br /> using namespace std;<br /> int map[100][100];//存储边权值<br /> bool inTree[100];<br /> int min_length[100];//非Tree结点和Tree中的结点间的min_distance<br /> int prim(int n)<br /> {<br /> int sum_length=0;<br /> memset(inTree,0,sizeof(inTree));<br /> for(int i=0;i<n;i++)//一开始，所有节点都是非Tree结点<br /> {<br /> min_length[i]=INT_MAX;<br /> }<br /> min_length[0]=0;//结点0作为起始结点<br /> for(int i=0;i<n;i++)<br /> {<br /> int min_index=-1;<br /> for(int j=0;j<n;j++)<br /> {<br /> if(!inTree[j]&&(min_index==-1||min_length[j]<min_length[min_index]))<br /> min_index=j;<br /> }<br /> inTree[min_index]=true;//将新寻找到的结点加到tree中，标记<br /> sum_length+=min_length[min_index];<br /> for(int j=0;j<n;j++)//将所有和min_index相连的非tree结点的min_distance更新<br /> {<br /> if(!inTree[j]&&map[min_index][j]<min_length[j])<br /> min_length[j]=map[min_index][j];<br /> }<br /> }<br /> return sum_length;<br /> }<br /> int main()<br /> {<br /> int n;<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> for(int i=0;i<n;i++)<br /> {<br /> for(int j=0;j<n;j++)<br /> {<br /> scanf("%d",&map[i][j]);<br /> }<br /> }<br /> printf("%d/n",prim(n));<br /> }<br /> return 0;<br /> }</p> <p>