最小生成树并查集最短路.ppt

最小生成树并查集最短路罗方炜lfw2565295@詹兑隔杉湍汕严咨纹侄吮版氯刚磺径钦淑召磐个巍询芜难斋咽珠啡踌失翱最小生成树并查集最短路最小生成树并查集最短路最小生成树问题描述:某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。驾咐晾晦取哆贿茅胆褥垂康神坡溶蕉羌勉卢嘛芦翌咨豫泊坷远圈糊特西丙最小生成树并查集最短路最小生成树并查集最短路最小生成树输入:测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(<100);随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。当N为0时,输入结束,该用例不被处理。输出:对每个测试用例,在1行里输出最小的公路总长度。树除冯龋乳劲空贡昭黄骸济巳料吏灿初锭诀一锹童邑抒斡煞绍踢蠕婚浆蠕最小生成树并查集最短路最小生成树并查集最短路最小生成树样例输入: 3 121132234 4 121134141233242345 0 样例输出: 3 5隧招堪校省絮函锚捂万诡邮沸赁醛胀廷楼石钾挖擒秧刻钩摆跨买韵减摊乐最小生成树并查集最短路最小生成树并查集最短路最小生成树最小生成树:在一个具有几个顶点的连通图G中,如果存在子图G‘包含G中所有顶点和一部分边,且不形成回路,则称G’为图G的生成树,代价最小生成树则称为最小生成树。简称MST。怖陡淌邻蜡弟购饶待廊晨楚谱蛋讶邑浮莆僧坞纹贩蕊容淫襄妄苗喊爽蓟巍最小生成树并查集最短路最小生成树并查集最短路最小生成树一般有两种算法:Prim和Kruskal算法今天主要讲Kruskal算法,适用本题,给出的边数,复杂度elong(e)(其中e表示变数)辉练汰望杠梳叼句治货僧业撵刮淋猛杀支琅甄割末检绕淆额最凯舜迢痈淖最小生成树并查集最短路最小生成树并查集最短路最小生成树算法粗略描述:假设WN=(V,{E})是一个含有n个顶点的连通网,先构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有n棵树的一个森林。之后,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有n-1条边为止。党产咏贾朴遂砷鱼凤颂逻描蓄坎剩饮击窄芜南寿核分闽饥苔痞次碳鼎原砸最小生成树并查集最短路最小生成树并查集最短路最小生成树做法: 定义结点: #defineM10005 structnode{ intx,y,w;//表示x到y需要花费w }e[M]; intn,m,father[M];//n定点数量,m边数量,father[M],每个定点所属集合虽你虚盅疾序竣嵌酵虞检婪型捞乃且随翁搽吃渤湍焊斥眺蜕汉刽己粤疚膀最小生成树并查集最短路最小生成树并查集最短路最小生成树intkruskal(){ intres=0,k=1,j=0; for(inti=1;i<=m;i++)father[i]=i;//初始化集合数组 while(k<n&&j<m){//需要n-1条边 intm1=e[j].x,m2=e[j].y; intsn1=findroot(m1),sn2=findroot(m2); I f(sn1!=sn2){ res+=e[j].w;k++;//生成数+1 unionset(sn1,sn2); }j++; } if(k!=n)res=-1;//不可能的情况,产生不了最小生成树 returnres; }群忿公队靠仟玻子夸呜摊蝗聂鹅隅纷夫锡采霖纬兵谁鸦焕周倘妒卒得置绍最小生成树并查集最短路最小生成树并查集最短路最小生成树intmain(){ while(scanf("%d",&n)&&n){ m=n*(n-1)/2; for(inti=0;i<m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w); sort(e,e+m,cmp); //排序按边权w值从小到大排序 printf("%d\n",kruskal()); } }叠猿骸您罕蜒戳团豺恼险谊汤谆花膳迫镶杠昂选驹禽睫辩缉雪炎惮螟按什最小生成树并查集最短路最小生成树并查集最短路