学步园

题意：给定一个N及N*N的矩阵，求最小生成树。

#include<cstdio><br /> #include<iostream><br /> using namespace std;<br /> #define maxcost 10000000<br /> int g[105][105];<br /> int n;<br /> int vis[105],dist[105];<br /> void prim(int v)<br /> {<br /> int i,j,min,dis,ans=0;<br /> memset(vis,true,sizeof(vis));<br /> for(i=0;i<n;i++)<br /> {<br /> dist[i]=g[v][i];<br /> }<br /> dist[v]=0;vis[v]=false;<br /> for(i=0;i<n;i++)<br /> {<br /> min=maxcost;int k=i;<br /> for(j=0;j<n;j++)<br /> if(dist[j]<min&&vis[j])<br /> {<br /> k=j;min=dist[j];<br /> }<br /> if(min!=maxcost)<br /> ans+=min;<br /> vis[k]=false;<br /> for(j=0;j<n;j++)<br /> {<br /> if(vis[j]&&dist[j]>g[k][j])<br /> dist[j]=g[k][j];<br /> }<br /> }<br /> printf("%d/n",ans);<br /> }<br /> int main()<br /> {<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> for(int i=0;i<n;i++)<br /> for(int j=0;j<n;j++)<br /> scanf("%d",&g[i][j]);<br /> prim(0);<br /> }<br /> return 0;<br /> }