首页 > Web开发 > 详细

[2016-03-19][UVALive][3027][Corporative Network]

时间:2016-03-19 14:20:42      阅读:235      评论:0      收藏:0      [点我收藏+]
  • 时间:2016-03-19 13:24:23 星期六

  • 题目编号:[2016-03-19][UVALive][3027][Corporative Network]

  • 题目大意:给定n个节点,I u v表示把u节点的父节点设置为v,距离为|u-v|%1000,E u表示询问u到根节点的距离,给定若干个I E操作,输出相应答案

  • 分析:带权并查集

  • 方法:d[maxn] 维护到父节点的距离,每次询问的时候,把当前节点压缩到根节点输出对应距离即可

  1. #ifdef _WORK_
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include<cstring>
  5. using namespace std;
  6. #define CLR(x,y) memset((x),(y),sizeof((x)))
  7. #define FOR(x,y,z) for(int (x)=(y);(x)<(z);++(x))
  8. const int maxn = 20000 +10;
  9. int fa[maxn],d[maxn];
  10. inline void ini(int n){
  11. CLR(d,0);
  12. FOR(i,0,n+1) fa[i] = i;
  13. }
  14. int fnd(int x){
  15. if(x == fa[x]) return x;
  16. int tmp = fa[x];
  17. fa[x] = fnd(fa[x]);
  18. d[x] = d[x] + d[tmp];
  19. return fa[x];
  20. }
  21. int main(){
  22. int t,n,p,q;
  23. char str[10];
  24. scanf("%d",&t);
  25. while(t--){
  26. scanf("%d",&n);
  27. ini(n);
  28. while(~scanf("%s",str) && str[0] != ‘O‘){
  29. if(str[0] == ‘I‘){
  30. scanf("%d%d",&p,&q);
  31. fa[p] = q;
  32. d[p] = abs(p - q)%1000;
  33. }else{
  34. scanf("%d",&p);
  35. fnd(p);
  36. printf("%d\n",d[p]);
  37. }
  38. }
  39. }
  40. return 0;
  41. }




[2016-03-19][UVALive][3027][Corporative Network]

原文:http://www.cnblogs.com/qhy285571052/p/61c1f535569220dfb7b920319b6b8935.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!