Posted on 2010-08-01 21:58
Uriel 阅读(392)
评论(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;
}