Posted on 2011-11-04 20:11
C小加 阅读(1465)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
NYOJ地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=431
并查集
训练赛的时候强出了这个题，没有过，月赛的时候获哥又拿上来了，结果还是没过。后来听获哥讲明白了，Find函数没有处理好。最后总结了一下，并查集的本质还是没有理解透彻，处理节点与根节点的关系时总是很混乱。
题意：一共有n个龙珠和n个城市，第i颗龙珠在第i座城市。下面有两种操作：T a b 将a龙珠所在的城市的所有龙珠移动到第b个龙珠所在的城市Q a 询问a龙珠所在的城市，这座城市有多少颗龙珠，a龙珠被移动了多少次思路：看懂题意后就知道用并查集了。询问的前两个问题都很好解决，有点难度的是第三个问题，龙珠被移动的次数。我用count数组统计每颗龙珠移动的次数，路径压缩后，每颗龙珠的父亲就是它所在的城市，如果这颗龙珠所在的城市所有的龙珠被移走的话，这座城市变成一座空城市，所以不会有龙珠再被移动到这座城市，就是说一座城市只能转移一次，假设a所在的城市的所有龙珠移动到了b，合并的时候统计这座城市移动的次数，那么统计龙珠的时候，只要统计它的父亲它的祖父一直到它的老祖，每个长辈的count和就是这颗龙珠的移动次数。所以在Union的时候让它父亲的count++，Find的时候让它遍历到根节点每次都加上一个长辈的count。写完后会感觉到，就是一个裸体的并查集。#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=10003;
int father[MAXN],sum[MAXN],count[MAXN];
void Init(int n)
{
for(int i=0;i<=n;i++)
{
father[i]=i;
sum[i]=1;
count[i]=0;
}
}
int Find(int x)
{
int temp;
if(x==father[x]) return x;
else
{
temp=father[x];
father[x]=Find(father[x]);
count[x]+=count[temp];
}
return father[x];
}
void Union(int a,int b)
{
int x=Find(a);
int y=Find(b);
if(x==y) return;
else
{
father[x]=y;
count[x]++;
sum[y]+=sum[x];
sum[x]=0;
}
}
int main()
{
//freopen("input","r",stdin);
//freopen("out","w",stdout);
int t,cnt=1;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d%d",&m,&n);
printf("Case %d:\n",cnt++);
Init(m);
while(n--)
{
char s1;
getchar();
scanf("%c",&s1);
if(s1=='T')
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
}
else
{
int p;
scanf("%d",&p);
int temp=Find(p);
printf("%d %d %d\n",temp,sum[temp],count[p]);
}
}
}
return 0;
}