Posted on 2010-08-01 21:58
Uriel 閱讀(405)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
數據結構
很久沒碰并查集，正好看見分類上還有一道就做了...
菜啊，并查集稍微變化了一下就被搞死了...
題意：有兩種操作：
E x 詢問節點x到他的根節點的長度
I x y 將節點y成為x的父節點 兩點間長度為abs(x-y)%1000
一直在想記錄路徑那里怎么改一下，搞來搞去還是不對，參考了CY的Blog之后恍然大悟... - -
用結構體存每個節點，結構體里有兩個變量，一個記錄該節點的父節點，一個記錄該節點到當前其父節點的距離
每次I x y 操作之后將x的父節點設為y，x, y之間的距離即為abs(x-y)%1000
每次E x 操作之后更新x的父節點，x到其父節點這一條線上的結點的父節點和與父節點的距離也依次更新
代碼如下：
//Problem: 1962 User: Uriel
//Memory: 516K Time: 610MS
//Language: G++ Result: Accepted
//Union-Find Set
//2010.08.01
#include<stdio.h>
#include<stdlib.h>
struct node
{
int f;
int sum;
}p[20010];
int findset(int x){
int i,ans=0;
for(i=x;p[i].f!=i;i=p[i].f)ans+=p[i].sum;
int s=ans;
while(x!=i){
int t=p[x].f,q=p[x].sum;
p[x].f=i;
p[x].sum=s;
s-=q;
x=t;
}
return ans;
}
int main(){
int i,j,k,x,y,n,m;
char str[10];
scanf("%d",&m);
while(m--){
scanf("%d",&n);
for(i=1;i<=n;i++){
p[i].f=i;
p[i].sum=0;
}
while(scanf("%s",str),str[0]!='O'){
if(str[0]=='E'){
scanf("%d",&x);
printf("%d\n",findset(x));
}
else if(str[0]=='I'){
scanf("%d %d",&x,&y);
p[x].f=y;
p[x].sum=abs(x-y)%1000;
}
}
}
return 0;
}