链接：http://codevs.cn/problem/1078/
题目描述 Description
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不会超过100000
输入描述 Input Description
第一行： 农场的个数，N（3<=N<=100）。
第二行..结尾: 接下来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们每行限制在80个字符以内，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为线路从第i个农场到它本身的距离在本题中没有意义。
输出描述 Output Description
只有一个输出，是连接到每个农场的光纤的最小长度和。
样例输入 Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
样例输出 Sample Output
28
算法分析：
这道题是典型的最小生成树模板题。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define MAXV 100 4 #define INF 100005 5 void prim(int **edges,int n,int v); 6 int main(int argc, char *argv[]) 7 { 8 int N,**edges; 9 int i,j; 10 scanf("%d",&N); 11 edges=(int **)malloc(sizeof(int*)*N); 12 for(i=0;i<N;i++) 13 edges[i]=(int *)malloc(sizeof(int)*N); 14 for(i=0;i<N;i++) 15 for(j=0;j<N;j++) 16 scanf("%d",&edges[i][j]); 17 prim(edges,N,0); 18 return 0; 19 } 20 void prim(int **edges,int n,int v) 21 { 22 int total=0; 23 int lowcost[MAXV]; 24 // lowcost[k]=0标记k已经加入U.另外，lowcost[k]=w表示从最小生成树的点到达k节点的最短边是w 25 int min; 26 int closest[MAXV],i,j,k; //对于某个节点i∈V-U， closest[i]=v表示节点i借助某条边依附于处在U中的节点v。 27 for (i=0;i<n;i++) //给lowcost[]和closest[]置初值 28 { 29 lowcost[i]=edges[v][i]; 30 closest[i]=v; //closest[i]=v表示当前状态下到达i点的最合适的经过点是v 31 } 32 for (i=1;i<n;i++) //找出n-1个顶点 33 { 34 min=INF; 35 for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k 36 if (lowcost[j]!=0 && lowcost[j]<min) 37 { 38 min=lowcost[j]; 39 k=j; //k记录最近顶点的编号 40 } 41 //printf(" 边(%d,%d)权为:%d\n",closest[k]+1,k+1,min); 42 total=total+min; 43 lowcost[k]=0; //标记k已经加入U 44 for (j=0;j<n;j++) //修改数组lowcost和closest 45 if (edges[k][j]!=0 && edges[k][j]<lowcost[j]) 46 { 47 lowcost[j]=edges[k][j]; 48 closest[j]=k; //closest[j]=k表示构造最小生成树过程中，当前状态下到达j节点最优的路径是经过k节点。 49 } 50 } 51 //printf("最小生成树权值之和：%d\n",total); 52 printf("%d\n",total); 53 }
