50212228海岛帝国：LYF的太空运输站
【试题描述】
最近，“购物券”WHT在“药师傅”帝国资源大会上提出了“SSTS”太空运输站计划。由于恐怖分子前些日子刚猖狂完，炸毁高楼无数，YSF不得不执行 WHT丧心病狂的计划，“演员”KLINT（众所周知，又一大土豪同学）捐赠了众多资源，和高级技术。太空运输站建成了，YSF任命LYF为站长，LJX 为副站长。第一波运输计划开始了！可是，当运输军队到达中转站金星时，遭到了盗取新技术的恐怖分子的袭击。由于没有足够的兵力，整个舰队全军覆没，LYF 损失惨重，恼羞成怒，随即决定让YSM和LJX调用一半星际舰队。可恐怖分子太强，再次损失惨重。YSF无奈，决定给“过路费”。但YSF是个贪财的人， 所以，YSF想让给的钱最少。他把这个难题交给了LYF，LYF又把这个任务交给了LJX，所以请你帮帮可怜的LYF，帮他编一个程序。另外，悬赏 10000000000000000000000000000000000$，所以赶快做吧！
【输入要求】
* 第一行：两个整数：n表示有n个城市，m表示有m条道路。
* 接下来的m行，每行三个整数：a，b，c表示从a星到达b星的路花费是c
【输出要求】
输出需要钱数最少方案
【输入实例】
6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2
【输出实例】
19
【其他说明】
n<=15,m<=18
40ms够了吧？
【试题分析】
仔细思考这一题，其实就是让银子用的越少越好。换句话说,就是让最少的边让图连接，让多余的边去掉。而定义是：如果一个连通无向图不包含回路，那么，就完全可以说这就是一棵树。在这里，我们讨论的是图的最小生成树。那么，问题来了：怎么选出这N-1条边，让边的总长度之和最短呢?我们一下就可以想到：我们自然可以选择最短的边，然后再选择次短的边……直到选完了所有N-1条边为止。我们可以先排序，这是最显而易见的方法。依次选择，直到选择了N-1条边让图联通为止。比较难于实现的是判断两个顶点是否有连通，否则就产生了回路，就不是树了。我们可以用以前的DFS或BFS来解决这个问题，但是，效率好像很低？上面要求40ms之内搞定，所以，还有一种更好的方法——并查集。将所有顶点放在一个并查集中。只需判断两个点是否在一个集合里（即是否拥有共同的祖先）。这样操作的时间复杂度仅为O（logN）。
----------------------------------------------------------【以下为转载内容】
这个算法叫Kruskal算法，求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的 具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的 过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶 点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
C语言代码：
1 #include "stdio.h" 2 #include "stdlib.h" 3 struct edge 4 { 5 int m; 6 int n; 7 int d; 8 }a[5010]; 9 int cmp(const void *a,const void *b)//按升序排列 10 { 11 return((struct edge*)a)->d - ((struct edge*)b)->d; 12 } 13 int main(void) 14 { 15 inti,n,t,num,min,k,g,x[100]; 16 printf("请输入顶点的个数："); 17 scanf("%d",&n); 18 t = n * ( n - 1 ) / 2; 19 for(i=0;i<=n;i++) 20 x[i]=i; 21 printf("请输入每条边的起始端点、权值：/n"); 22 for(i=0;i<t;i++) 23 scanf("%d%d%d",&a[i].m,&a[i].n,&a[i].d);//输入每条边的权值 24 qsort(a,t,sizeof(a[0]),cmp); 25 min=num=0; 26 for(i=0;i<t && num < n-1;i++) 27 { 28 for(k=a[i].m;x[k]!=k;k=x[k])//判断线段的起始点所在的集合 29 x[k]=x[x[k]]; 30 for(g=a[i].n;x[g]!=g;g=x[g])//判断线段的终点所在的集合 31 x[g]=x[x[g]]; 32 if(k!=g)//如果线段的两个端点所在的集合不一样 33 { 34 x[g]=k; 35 min+=a[i].d; 36 num++; 37 printf("最小生成树中加入边：%d%d/n",a[i].m,a[i].n); 38 } 39 } 40 printf("最小生成树的权值为：%d/n",min); 41 system("pause"); 42 return 0; 43 }
kruskal算法的基本思想：
1.首先将G的n个顶点看成n个孤立的连通分支（n个孤立点）并将所有的边按权从小大排序。
2.按照边权值递增顺序，如果加入边后存在圈则这条边不加，直到形成连通图对2的解释：如果加入边的两个端点位于不同的连通支，那么这条边可以顺利加入而不会形成圈
本例中用到的图：
这个算法执行的过程就是按照规定一个个连通支合并的过程，使最后只剩一个连通支。
【以上内容为转载】
【代码】
1 #include<iostream> 2 using namespace std; 3 int dis[20],book[20]={0}; 4 int h[20],pos[20],size; 5 void swap(int x,int y) 6 { 7 int t; 8 t=h[x]; 9 h[x]=h[y]; 10 h[y]=t; 11 t=pos[h[x]]; 12 pos[h[x]]=pos[h[y]]; 13 pos[h[y]]=t; 14 return ; 15 } 16 void siftdown(int i) 17 { 18 int t,flag=0; 19 while(i*2<=size&&flag==0) 20 { 21 if(dis[h[i]]>dis[h[i*2]]) t=i*2; 22 else t=i; 23 if(i*2+1<=size) 24 if(dis[h[t]]>dis[h[i*2+1]]) t=i*2+1; 25 if(t!=i) 26 { 27 swap(t,i); 28 i=t; 29 } 30 else flag=1; 31 } 32 return ; 33 } 34 void siftup(int i) 35 { 36 int flag=0; 37 if(i==1) return ; 38 while(i!=1&&flag==0) 39 { 40 if(dis[h[i]]<dis[h[i/2]]) swap(i,i/2); 41 else flag=1; 42 i/=2; 43 } 44 return ; 45 } 46 int pop() 47 { 48 int t; 49 t=h[1]; 50 pos[t]=0; 51 h[1]=h[size]; 52 pos[h[1]]=1; 53 size--; 54 siftdown(1); 55 return t; 56 } 57 int main() 58 { 59 int n,m,i,j,k; 60 int u[30],v[30],w[30],first[20],next[30]; 61 int inf=9999999; 62 int count=0,sum=0; 63 scanf("%d%d",&n,&m); 64 for(i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]); 65 for(i=m+1;i<=2*m;i++) 66 { 67 u[i]=v[i-m]; 68 v[i]=u[i-m]; 69 w[i]=w[i-m]; 70 } 71 for(i=1;i<=n;i++) first[i]=-1; 72 for(i=1;i<=2*m;i++) 73 { 74 next[i]=first[u[i]]; 75 first[u[i]]=i; 76 } 77 book[1]=1; 78 count++; 79 dis[1]=0; 80 for(i=2;i<=n;i++) dis[i]=inf; 81 k=first[1]; 82 while(k!=-1) 83 { 84 dis[v[k]]=w[k]; 85 k=next[k]; 86 } 87 size=n; 88 for(i=1;i<=size;i++) 89 { 90 h[i]=i; 91 pos[i]=i; 92 } 93 for(i=size/2;i>=1;i--) 94 { 95 siftdown(i); 96 } 97 pop(); 98 while(count<n) 99 { 100 j=pop(); 101 book[j]=1; 102 count++; 103 sum+=dis[j]; 104 k=first[j]; 105 while(k!=-1) 106 { 107 if(book[v[k]]==0&&dis[v[k]]>w[k]) 108 { 109 dis[v[k]]=w[k]; 110 siftup(pos[v[k]]); 111 } 112 k=next[k]; 113 } 114 } 115 printf("%d",sum); 116 }
原文：http://www.cnblogs.com/wxjor/p/5605936.html
