acm必做50题的解题-并查集

《acm必做50题的解题-并查集》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACM必做50题的解题-并查集ACM必做50题的解题-并查集.txt两人之间的感情就像织毛衣，建立的时候一针一线，小心而漫长，拆除的时候只要轻轻一拉。。。。poj1861Network题意:Andrew要在公司里用电缆连接n个集线器，要用总长度最小的线连接，求出其中最长的那根电缆。也就是告诉n个顶点，m条边，求最小生成树的最大边。并把生成树的每条边输出来，Sample里面的输出有问题，应该是三条。给出节点个数m和边数n，下面n行给出边(x,y)以及权值w。输出第一行为最小生成树中的最大边权值，第二行为一个可行生成树方案的边数k，

2、下面k行为可行生成树的k条边。题目是SpecialJudge，意思就是不具有唯一解，可能有多解，样例输出为以下结果也可算对。13132423一样按照Kruskal解题即可，结果虽然不唯一，但是最小生成树一定是可行解之一。将边加入生成树时记录最大权值和边信息然后输出即可。#include#include#defineMAX15001/*定义边(x,y)，权为w*/typedefstruct{intx,y;intw;}edge;edgee[MAX];edgev[MAX];/*rank[x]表示x

3、的秩*/intrank[MAX];/*father[x]表示x的父节点*/intfather[MAX];/*比较函数，按权值非降序排序*/intcmp(constvoid*a,constvoid*b){return(*(edge*)a).w-(*(edge*)b).w;}/*初始化集合*/voidMake_Set(intx){father[x]=x;rank[x]=0;}/*查找x元素所在的集合,回溯时压缩路径*/intFind_Set(intx){if(x!=father[x]){father[x]=Find_Set(fath

4、er[x]);}returnfather[x];}/*合并x,y所在的集合*/voidUnion(intx,inty){if(x==y)return;if(rank[x]>rank[y]){father[y]=x;}else{if(rank[x]==rank[y]){rank[y]++;}father[x]=y;}}intmain(){inti,j,m,n,k,max;intx,y;scanf("%d%d",&m,&n);/*读入边数据*/for(i=0;i

5、.y,&e[i].w);}/*初始化集合*/for(i=0;i

6、"%d",k);for(i=1;i<=k;i++){printf("%d%d",v[i].x,v[i].y);}//system("pause");return0;}poj1182食物链建议：做此题之前先做poj2524和poj1611。这两道题都是并查集的基础应用。关键词：并查集相对关系思路：（用一个并查集就够了，同时对每个节点保持其到根结点的相对类别偏移量）1.p[x]表示x的根结点。r[x]表示p[x]与x的关系。r[x]==0表示p[x]与x同类；1表示p[x]吃x；2表示x吃p[x]。2.怎样划分一个集合呢？注

7、意，这里不是根据x与p[x]是否是同类来划分。而是根据“x与p[x]能否确定两者之间的关系”来划分，若能确定x与p[x]的关系，则它们同属一个集合。3.怎样判断一句话是不是假话？假设已读入D,X,Y,先利用find_set()函数得到X,Y所在集合的代表元素rx,ry,若它们在同一集合（即rx==ry）则可以判断这句话的真伪（据2.）.若D==1而r[X]!=r[Y]则此话为假。（D==1表示X与Y为同类，而从r[X]!=r[Y]可以推出X与Y不同类。矛盾。）若D==2而r[X]==r[Y]（X与Y为同类）或者　r[X]==(r

8、[Y]+1)%3（Y吃X）则此话为假。4.上个问题中r[X]==(r[Y]+1)%3这个式子怎样推来？假设有Y吃X，那么r[X]和r[Y]的值是怎样的？　我们来列举一下:r[X]=0&&r[Y]=2r[X]=1&&r[Y]=0r[X]=2&&r[Y]=1稍微观察