July 6——3635

http://acm.hdu.edu.cn/showproblem.php?pid=3635

题目:有N个龙珠,放在N个城市,由于时间太久,龙珠发生了移动,对于T操作,是把b 城市的龙珠移到a城市,经过若干操作后,问第A个球所在的城市,以及这个城市的龙珠的个数,和这个龙珠总共发生了多少次转移。


解:此题宜用并查集来解:

   首先1-n初始化,father[i]=i;  //城市序号

                                 num[i]=1;   //龙珠个数

                                 c[i]=0;        //转移次数

    在查找根节点时,对龙珠转移次数进行累加

                                  int t=father[x];

                                   c[x]+=c[t];

    合并时

                 number[y]+=number[x];

                 c[x]++;                     //  每合并一次都要进行累加

                 number[x]=0;         //转移之后,该城市龙珠为0;

#include<iostream>
using namespace std;
#include<stdio.h>
#define N 10000+2
int n,m;

int father[N],number[N],num[N];
void initialize()
{
for(int i=1;i<=n;i++)
{
father[i]=i;
number[i]=1;
num[i]=0;
}
}

int find(int x)
{
int t=father[x];
if(x!=father[x])
{
father[x]=find(father[x]);
num[x]+=num[t];
}
return father[x];
}

void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return;
else
{
father[x]=y;
number[y]+=number[x];
num[x]++;
number[x]=0;
}
}

int main()
{
int t,a,b,k=1;
char str[4];
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d",&n,&m);
initialize();
printf("Case %d:\n",k);
while(m--)
{
scanf("%s",&str);
if(str[0]=='T')
{
scanf("%d%d",&a,&b);
unite(a,b);
// cout<<" asdklggsd;lsdakg;l"<<endl;
}
else
{
scanf("%d",&a);
int p=find(a);
printf("%d %d %d\n",p,number[p],num[a]);
}
}
}
return 0;
}



评论

© 现实给了梦想多少时间 | Powered by LOFTER