开发者社区云计算文章正文

uva 1329 Corporative Network

2013-07-26 883

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 点击打开链接uva 1329 思路: 带权并查集分析: 1 看懂题目就是切菜了代码: #include#include#include#includeusing namespace std;const int MAXN...

点击打开链接uva 1329

思路: 带权并查集
分析:
1 看懂题目就是切菜了

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 20010;

int n;
int father[MAXN];
int rank[MAXN];

void init(){
    memset(rank , 0 , sizeof(rank));
    for(int i = 1 ; i < MAXN ; i++)
        father[i] = i;
}

int find(int x){
    if(father[x] == x)
        return x;
    int tmp = father[x];
    father[x] = find(father[x]);
    rank[x] += rank[tmp];
    return father[x];
}

int main(){
    int Case;
    char c;
    int x , y;
    scanf("%d" , &Case);
    while(Case--){
         init();
         scanf("%d%*c" , &n); 
         while(scanf("%c" , &c) && c != 'O'){
              if(c == 'E'){
                  scanf("%d%*c" , &x);
                  int tmp = find(x);
                  printf("%d\n" , rank[x]);
              }
              else{
                  scanf("%d%d%*c" , &x , &y); 
                  int fx = find(x); 
                  int fy = find(y); 
                  if(fx != fy){
                     father[fx] = fy;
                     rank[fx] = abs(x-y)%1000+rank[y]-rank[x];
                  }
              } 
         }
    }
    return 0;
}