欢迎来到天天文库
浏览记录
ID:14399443
大小:43.00 KB
页数:17页
时间:2018-07-28
《acm必做50题的解题-并查集》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ACM必做50题的解题-并查集ACM必做50题的解题-并查集.txt两人之间的感情就像织毛衣,建立的时候一针一线,小心而漫长,拆除的时候只要轻轻一拉。。。。poj1861Network题意:Andrew要在公司里用电缆连接n个集线器,要用总长度最小的线连接,求出其中最长的那根电缆。也就是告诉n个顶点,m条边,求最小生成树的最大边。并把生成树的每条边输出来,Sample里面的输出有问题,应该是三条。给出节点个数m和边数n,下面n行给出边(x,y)以及权值w。输出第一行为最小生成树中的最大边权值,第二行为一个可行生成树方案的边数k,下面k行为可行生成
2、树的k条边。题目是SpecialJudge,意思就是不具有唯一解,可能有多解,样例输出为以下结果也可算对。13132423一样按照Kruskal解题即可,结果虽然不唯一,但是最小生成树一定是可行解之一。将边加入生成树时记录最大权值和边信息然后输出即可。#include#include#defineMAX15001/*定义边(x,y),权为w*/typedefstruct{intx,y;intw;}edge;edgee[MAX];edgev[MAX];/*rank[x]表示x的秩*/intrank[MAX];/
3、*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(father[x]);}returnfather[x];}/*
4、合并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;i5、+){Make_Set(i);}/*对边排序*/qsort(e,n,sizeof(edge),cmp);k=0;max=0;for(i=0;i6、[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.怎样划分一个集合呢?注意,这里不是根据x与p[x]是否是同类来划分。而是根据“x与p[x]能否确定两者之间的关系”来划分,若能确定7、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[Y]+1)%3(Y吃X)则此话为假。4.上个问题中r[X]==(r[Y]+1)%3这个式子怎样推来?假设有Y吃X,那么r[X8、]和r[Y]的值是怎样的? 我们来列举一下:r[X]=0&&r[Y]=2r[X]=1&&r[Y]=0r[X]=2&&r[Y]=1稍微观察
5、+){Make_Set(i);}/*对边排序*/qsort(e,n,sizeof(edge),cmp);k=0;max=0;for(i=0;i6、[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.怎样划分一个集合呢?注意,这里不是根据x与p[x]是否是同类来划分。而是根据“x与p[x]能否确定两者之间的关系”来划分,若能确定7、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[Y]+1)%3(Y吃X)则此话为假。4.上个问题中r[X]==(r[Y]+1)%3这个式子怎样推来?假设有Y吃X,那么r[X8、]和r[Y]的值是怎样的? 我们来列举一下:r[X]=0&&r[Y]=2r[X]=1&&r[Y]=0r[X]=2&&r[Y]=1稍微观察
6、[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.怎样划分一个集合呢?注意,这里不是根据x与p[x]是否是同类来划分。而是根据“x与p[x]能否确定两者之间的关系”来划分,若能确定
7、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[Y]+1)%3(Y吃X)则此话为假。4.上个问题中r[X]==(r[Y]+1)%3这个式子怎样推来?假设有Y吃X,那么r[X
8、]和r[Y]的值是怎样的? 我们来列举一下:r[X]=0&&r[Y]=2r[X]=1&&r[Y]=0r[X]=2&&r[Y]=1稍微观察
此文档下载收益归作者所有