昨天做了ZOJ1372，挺开心的，又学了一个算法——最小生成树的prim算法。 其实这个算法跟最短路径算法差不了多少，只是其中改了一点点条件。 这样说吧。比如最短路的起点是1号点，那么数组每次更新的都是到1号点的最短距离。 而最小生成树则是到已选的当前点集的最短距离。 两个都是贪心算法的经典。 学的不多，不过每天都在快乐地进步。 上代码：#include <stdio.h> #include <string.h> int mat[55][55],used[55],min[55]; int p; int prim() { int i,j,k,q,ret = 0; for(i = 1;i <= p;i++) min[i] = 1000000000,used[i] = 0; min[1] = 0; for(i = 1;i <= p;i++) { k = -1; for(j = 1;j <= p;j++) if(!used[j] && (k == -1 || min[j] < min[k])) k = j; used[k] = 1; ret += min[k]; for(j = 1;j <= p;j++) if(!used[j] && mat[k][j] && mat[k][j] < min[j]) min[j] = mat[k][j]; } return ret; } int main() { int i,j,n,r,a,b,c; while(scanf("%d%d",&p,&r) != EOF && p != 0) { memset(mat,0,sizeof(mat)); for(i = 0;i < r;i++) { scanf("%d%d%d",&a,&b,&c); if(!mat[a][b] || mat[a][b] > c) mat[a][b] = mat[b][a] = c; } printf("%d\n",prim()); } return 0; }  

评论