Posted on 2010-08-01 21:58
Uriel 閱讀(400)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
數(shù)據(jù)結(jié)構(gòu)
很久沒碰并查集，正好看見分類上還有一道就做了...
菜啊，并查集稍微變化了一下就被搞死了...
題意：有兩種操作：
E x 詢問節(jié)點(diǎn)x到他的根節(jié)點(diǎn)的長(zhǎng)度
I x y 將節(jié)點(diǎn)y成為x的父節(jié)點(diǎn) 兩點(diǎn)間長(zhǎng)度為abs(x-y)%1000
一直在想記錄路徑那里怎么改一下，搞來搞去還是不對(duì)，參考了CY的Blog之后恍然大悟... - -
用結(jié)構(gòu)體存每個(gè)節(jié)點(diǎn)，結(jié)構(gòu)體里有兩個(gè)變量，一個(gè)記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)，一個(gè)記錄該節(jié)點(diǎn)到當(dāng)前其父節(jié)點(diǎn)的距離
每次I x y 操作之后將x的父節(jié)點(diǎn)設(shè)為y，x, y之間的距離即為abs(x-y)%1000
每次E x 操作之后更新x的父節(jié)點(diǎn)，x到其父節(jié)點(diǎn)這一條線上的結(jié)點(diǎn)的父節(jié)點(diǎn)和與父節(jié)點(diǎn)的距離也依次更新
代碼如下：
//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;
}