最小生成树（Prim算法）

/* 1 0

2 3 1 2 37 2 1 17 1 2 68 3 7 1 2 19 2 3 11 3 1 7 1 3 5 2 3 89 3 1 91 1 2 32 5 7 1 2 5 2 3 7 2 4 8 4 5 11 3 5 10 1 5 6 4 2 12 0

Sample Output

0 17 16 26 */ #include<stdio.h> #include<string.h> #define N 1005 #define INF 0x3f3f3f int cost[N][N];//结点u到v的权值 int mincost[N];//在集合S中第一个节点到N的节点的最小权值 bool s[N];//标记是结点是否加入到了集合S中 int n,m; int Prim() { int i,u; for(i=1;i<n+1;++i){ mincost[i]=INF; s[i]=false; } mincost[1]=0; int res=0; while(true){//这个永真式可以换成一个for循环n-1次并且第一个if int v=-1; //要变下 for(u=1;u<n+1;++u){ if(!s[u]&&(v==-1||mincost[u]<mincost[v])){ v=u; } } if(v==-1)break; s[v]=true; res+=mincost[v]; for(u=1;u<n+1;++u){ mincost[u]=mincost[u]<cost[v][u]?mincost[u]:cost[v][u]; } } return res; } int main() { while(~scanf("%d",&n)&&n){ scanf("%d",&m); memset(cost,INF,sizeof(cost)); for(int i=0;i<m;++i){ int a,b,c; scanf("%d%d%d",&a,&b,&c); cost[a][b]=cost[a][b]<c? cost[a][b]:c; cost[b][a]=cost[a][b]; } printf("%d\n",Prim()); } return 0; }