链接: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
算法分析:
这道题是典型的最小生成树模板题。
prim算法:
1 #include <stdio.h> 2 #include<limits.h> 3 4 //Prim算法求最小生成树 5 const int maxn=101; //顶点个数最大值 6 int Prim(int n,int dist[maxn],int map[maxn][maxn],int pre[maxn]) 7 //n个顶点,dist[i]表示向外延伸的最短边长,map记录图信息,pre记录连接信息 8 { 9 int total=0; 10 int i,j,k; 11 int min; 12 bool p[maxn];//p[i]=true表示顶点i属于集合Va,反之属于集合Vb。 13 14 for(i=2;i<=n;i++)//初始化 15 { 16 p[i]=false; 17 dist[i]=map[1][i]; 18 pre[i]=1; 19 } 20 dist[1]=0; //从顶点1开始,把顶点1放入Va集合 21 p[1]=true; 22 23 for(i=1;i<n;i++)//循环n-1次,每次加入一个点到最小生成树的顶点集Va。 24 { 25 min=INT_MAX; 26 k=0; 27 for(j=1;j<=n;j++)//寻找属于Vb集合而且距离最近的那个点 28 { 29 if(!p[j]&&dist[j]<min) 30 { 31 min=dist[j]; 32 k=j; 33 } 34 } 35 if(k==0) return -1;//假如没有点可以扩展,说明图G不连通,直接返回 36 p[k]=true; 37 total=total+min; 38 //printf("(%d,%d,%d) ",pre[k],k,min); 39 40 //遍历所以与顶点k邻接的、而且属于集合Vb的顶点j,更新到达j的距离以及到达j的最近的点 41 for(j=1;j<=n;j++) 42 { 43 if(!p[j]&&map[k][j]!=INT_MAX&&map[k][j]<dist[j]) 44 { 45 dist[j]=map[k][j]; 46 pre[j]=k; 47 } 48 } 49 } 50 return total; 51 } 52 53 int main(int argc, char *argv[]) 54 { 55 int N,map[maxn][maxn],dist[maxn],pre[maxn]; 56 int i,j,res; 57 freopen("data.in","r",stdin); 58 scanf("%d",&N); 59 for(i=1;i<=N;i++) 60 for(j=1;j<=N;j++) 61 scanf("%d",&map[i][j]); 62 res=Prim(N,dist,map,pre); 63 printf("%d ",res); 64 return 0; 65 }
下面是另一个版本的prim算法代码:
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 ",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 ",total); 52 printf("%d ",total); 53 }
下面是kruskal算法实现的代码:
1 #include <stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 6 //并查集 7 const int maxn=1010;//最大顶点个数 8 int UFSTree[maxn]; 9 void initUFSTree()//初始化并查集的数组 10 { 11 for(int i=0;i<maxn;i++) UFSTree[i]=i; 12 } 13 int find(int x)//查找x所在的团队的队长 14 { 15 int root=x; 16 while(UFSTree[root]!=root) root=UFSTree[root]; 17 18 int i=x,j; 19 while(i!=root) 20 { 21 j=UFSTree[i]; 22 UFSTree[i]=root; 23 i=j; 24 } 25 return root; 26 } 27 void merge(int x,int y)//合并x和y所在的两个团队 28 { 29 int fx=find(x),fy=find(y); 30 if(fx!=fy) UFSTree[x]=y; 31 } 32 33 //kruskal算法:利用前向星结构存储图 34 const int maxe=100010;//边的最大条数 35 struct node 36 { 37 int from,to;//一条边的起点和终点 38 int w;//边的权值 39 int selected;//标记该条边是否已经被选择 40 }edge[maxe]; 41 bool cmp(node a,node b) 42 { 43 if(a.w!=b.w) return a.w<b.w; 44 if(a.from!=b.from) return a.from<b.from; 45 return a.to<b.to; 46 } 47 int kruskal(node *edge,int n,int m) 48 { 49 int total=0;//最小生成树的权值总和 50 int k=0;//记录目前为止已经合并了多少条边 51 int i,x,y; 52 sort(edge+1,edge+1+m,cmp); 53 for(i=1;i<=m;i++) 54 { 55 if(k==n-1) break;//已经合并了n-1条边,最小生成树已经构造好,可以返回。 56 x=find(edge[i].from); 57 y=find(edge[i].to); 58 if(x!=y) 59 { 60 merge(x,y); 61 k++; 62 edge[i].selected=true; 63 total=total+edge[i].w; 64 } 65 } 66 return total; 67 } 68 int main() 69 { 70 int N,M=0; 71 int i,j,temp,res; 72 freopen("data.in","r",stdin); 73 scanf("%d",&N); 74 for(i=1;i<=N;i++) 75 for(j=1;j<=N;j++) 76 { 77 scanf("%d",&temp); 78 if(i!=j) 79 { 80 M++; 81 edge[M].from=i; 82 edge[M].to=j; 83 edge[M].w=temp; 84 edge[M].selected=false; 85 } 86 } 87 initUFSTree(); 88 res=kruskal(edge,N,M); 89 printf("%d ",res); 90 return 0; 91 }