Posted on 2011-11-04 20:11
C小加 閱讀(1474)
評論(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;
}