随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:  龙珠在哪里,那里有多少龙珠,目标龙珠移动了多少次。移动龙珠,并将在一起的龙珠同时移动。
 4 How to Do:  T A B即将Ath龙珠所在地所有龙珠移动到Bth龙珠所在地
 5             Q A显示Ath龙珠所在地ID及此地的龙珠数和Ath龙珠的移动次数  
 6   */
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #define MAXSIZE 200001
10 int n,q;
11 struct ball{
12     int id;//所在城市编号
13     int par;//同在一座城市的上一节点
14     int trans;//该龙珠的移动次数
15 }lz[MAXSIZE];
16 int counts[MAXSIZE];//某城市的龙珠数目
17 char ch;
18 
19 int findSet(int x){
20     int t=lz[x].par;
21     if(lz[x].par!=x)
22         lz[x].par=findSet(lz[x].par);
23     lz[x].trans+=lz[t].trans;
24     return lz[x].par;
25 }
26 inline void merge(int x,int y){//从xth所在城市到yth所在城市
27     int px=findSet(x);
28     int py=findSet(y);
29     if(px==py)    return;
30     counts[lz[py].id]+=counts[lz[px].id];
31     counts[lz[px].id]=0;
32     lz[px].id=lz[py].id;
33     lz[px].par=py;
34     lz[px].trans++;
35 }
36 inline void makeSet(int n){
37     int i;
38     for(i=1;i<=n;i++)//从1到n
39         lz[i].id=i,lz[i].par=i,lz[i].trans=0,counts[i]=1;
40 }
41 inline void scan(int &x){
42     while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
43     while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
44 }
45 int main(){
46     freopen("in.txt","r",stdin);
47     int t,no=1;
48     scan(t);
49     while (t--){
50         printf("Case %d:\n",no++);
51         scan(n);
52         scan(q);
53         makeSet(n);
54         while (q--){
55             char s;    int a,b;
56             while (s=getchar(),s<'A'||s>'Z');
57             scan(a);
58             if (s=='T'){
59                 scan(b);
60                 merge(a,b);    
61                 continue;
62             }
63             int tt=findSet(a);
64             printf("%d %d %d\n",lz[tt].id,counts[lz[tt].id],lz[a].trans);            
65         }
66     }
67     return 0;
68 }
69 
70 
posted on 2012-03-21 22:10 Leo.W 阅读(210) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理