欢迎来到天天文库
浏览记录
ID:37916764
大小:33.00 KB
页数:4页
时间:2019-06-02
《Pku1998并查集题解题报告》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、Pku1998CubeStacking/*Name:pku1998Copyright:ecjtu_acmAuthor:yimaoDate:22-08-1009:19Description:并查集*/一、题目DescriptionFarmerJohnandBetsyareplayingagamewithN(1<=N<=30,000)identicalcubeslabeled1throughN.TheystartwithNstacks,eachcontainingasinglecube.FarmerJohnasksBetsytoperformP(1<=P<=100,000)ope
2、ration.Therearetwotypesofoperations:movesandcounts.*Inamoveoperation,FarmerJohnasksBessietomovethestackcontainingcubeXontopofthestackcontainingcubeY.*Inacountoperation,FarmerJohnasksBessietocountthenumberofcubesonthestackwithcubeXthatareunderthecubeXandreportthatvalue.Writeaprogramthatcanve
3、rifytheresultsofthegame.Input*Line1:Asingleinteger,P*Lines2..P+1:Eachoftheselinesdescribesalegaloperation.Line2describesthefirstoperation,etc.Eachlinebeginswitha'M'foramoveoperationora'C'foracountoperation.Formoveoperations,thelinealsocontainstwointegers:XandY.Forcountoperations,thelinealso
4、containsasingleinteger:X.NotethatthevalueforNdoesnotappearintheinputfile.Nomoveoperationwill4requestamoveastackontoitself.OutputPrinttheoutputfromeachofthecountoperationsinthesameorderastheinputfile.SampleInput6M16C1M24M26C3C4SampleOutput102二、题目大意及分析【题意】摘自《ACM程序设计竞赛入门》。有n个独立的磁铁(1-n标号)放在桌上,一
5、个人对这n堆进行移动操作,然后另一个人询问。规则:M:将含有编号为X的磁铁放在包含Y的顶端上;C:询问在编号Z下面磁铁的数目;【分析】利用并查集,每一堆磁铁看作一个集合,“Mab”就是将a归并到b的上面,每个集合是有序的。设定3个域Father:根节点,初始化为本身;Num:以该节点为根的集合的元素个数;Dis:该点到其根的距离;那么由num[father[a]]-dis[a]-1就是以a节点为根的集合所含有的元素个数。三、代码及相关说明/*1988Accepted736K610MSG++1023B2010-08-2209:06:36*//*1988Accepted516K2
6、97MSC++1023B2010-08-2209:07:03*/4#include#definearr30005intfather[arr],num[arr],dis[arr];//查找根节点;intfind(intx){if(x!=father[x]){inttemp=father[x];father[x]=find(father[x]);dis[x]+=dis[temp];}returnfather[x];}//把a放在b上面;father_b改变;voidunion_set(inta,intb){intf_a=find(a),f_b=find(b);f
7、ather[f_b]=f_a;dis[f_b]=num[f_a];num[f_a]+=num[f_b];}intmain(){intN,i,a,b;charch[3];while(scanf("%d",&N)!=EOF){for(i=1;i
此文档下载收益归作者所有