HDU 4829 Information [带权并查集]【数据结构】
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4829 Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Input Output Sample Input Sample Output Source ——————————————————————————–. 解题思路: 就是维护一堆数据之间的关系,读完题很容易想到带权并查集,权值为两个点之间的相对距离.但是在维护上不是怎么好维护啊。 不好维护的地方 解决; 解决了上述几个问题,这道题就不难解决了. 附本题代码 #include <bits/stdc++.h>
using namespace std;
const int N = 100000*2+7;
/***********************************************************************/
int pre[N],h[N],hh;
struct node {
int x,y;
}p[N];
int findi(int x){
if(pre[x]==x) return x;
int r = findi(pre[x]);
p[x].x+=p[pre[x]].x;
p[x].y+=p[pre[x]].y;
pre[x]=r;
return r;
}
void join(int x,int y,int X,int Y){
int fx = findi(x),fy = findi(y);
pre[fx]=fy;
p[fx].x=p[y].x+X-p[x].x;
p[fx].y=p[y].y+Y-p[x].y;
return ;
}
void creat(int now){
h[now]=++hh;
pre[hh]=hh;
p[hh].x=0;
p[hh].y=0;
}
int main(){
int _,n,m,kcase = 0;
scanf("%d",&_);
while(_--){
int n;
scanf("%d",&n);printf("Case #%d:n",++kcase);
hh=-1;
for(int i=0;i<=n;i++) creat(i),h[i]=i;
for(int i=n+1;i<=(n<<1);i++) p[i].x=p[i].y=0;
int x,y,a,b,op;
for(int i=1;i<=n;i++){
scanf("%d",&op);b=0;
if(op==1||op==2){
if(op==1)scanf("%d%d%d%d",&a,&b,&x,&y);
else scanf("%d%d%d",&y);
creat(a);
join(h[a],h[b],x,y);
}
else if(op==3||op==4){
if(op==3)scanf("%d%d%d%d",&y);
a=h[a],b=h[b];
if(findi(a)==findi(b)){if(x!=p[a].x-p[b].x||y!=p[a].y-p[b].y)puts("REJECT");}
else join(a,y);
}
else {
if(op==5)scanf("%d%d",&b);
else scanf("%d",&a);
a=h[a],b=h[b];
if(findi(a)!=findi(b)) {puts("UNKNOWN");continue; }
else printf("%d %dn",p[a].x-p[b].x,p[a].y-p[b].y);
}
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- unix – 使用/usr/bin/time时如何忽略程序的输出?
- 在OPhone 中使用KSOAP2调用WebService
- Webservice-基于JWS初级实例(二)
- Angular2 – 从外部验证并提交表单
- angular2.js:2 Uncaught ReferenceError: System is not de
- vim – 当filetype为none时,如何设置autocmd生效?
- 【数据结构】BitMap使用
- twitter-bootstrap – 始终显示bootstrap-datepicker,而不仅
- unix – 只打印匹配的单词,而不是整行通过grep
- angularjs – 如何获取在ui-select搜索框中输入的值?