M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

TOJ 1688. Corporative Network 并查集

       这道题题意很难懂,大意是有N个公司,每个公司有一个center,最初每个公司的center都在自己公司,然后有M次操作,每次操作 A , B (A保证是一个集合的center,B不一定) 表示将A所在的集合并到B所在的集合,且B的center成为了A的center。每次操作后两个公司的线的距离增加abs(A-B)%1000;
Sample Input: (E  P表示查询P距离自己center的线的长度,I   P  Q 表示合并 P ,Q);
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
Sample Output:
0
2
3
5

Code:
#include <cstdio>
#include 
<iostream>
#define M 20010
using namespace std;

struct Node{
        
int father,num;
}a[M];
void initial(int n){
        
int i;
        
for(i = 1;i <= n; i++){
                a[i].father 
= i;
                a[i].num 
= 0;
        }
}
int find(int n){
        
int tep,m = n;
        
if(n == a[n].father) return n;
        find(a[n].father);               
//递归查找n的祖先
        a[n].num += a[a[n].father].num;   //n的直需要更新(加上n的父亲的值)
        a[n].father = a[a[n].father].father;
}
int main()
{
        
int T,n,i,j,k;
        
char order[3];
        scanf(
"%d",&T);
        
while(T--){
                scanf(
"%d",&n);
                initial(n);
                
while(scanf("%s",order)){
                        
if(order[0]== 'O'break;
                        
if(order[0== 'E'){
                                scanf(
"%d",&k);
                                find(k);
                                printf(
"%d\n",a[k].num);
                        }
                        
else{
                                scanf(
"%d%d",&j,&k);
                                
int dis = abs(j-k)%1000;
                                a[j].num 
= dis;           //该值dis为j的值
                                a[j].father = k;          //k成为了j的父亲
                        }
                }
        }
}





posted on 2010-07-05 20:48 M.J 阅读(123) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理