• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            C小加

            厚德 博學 求真 至善 The bright moon and breeze
            posts - 145, comments - 195, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            hdu 3635 NYOJ 431 Dragon Balls 解題報告

            Posted on 2011-11-04 20:11 C小加 閱讀(1474) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            NYOJ地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=431
            并查集
            訓練賽的時候強出了這個題,沒有過,月賽的時候獲哥又拿上來了,結果還是沒過。后來聽獲哥講明白了,Find函數沒有處理好。最后總結了一下,并查集的本質還是沒有理解透徹,處理節點與根節點的關系時總是很混亂。 

            題意:一共有n個龍珠和n個城市,第i顆龍珠在第i座城市。下面有兩種操作:
            T a b 將a龍珠所在的城市的所有龍珠移動到第b個龍珠所在的城市
            Q a 詢問a龍珠所在的城市,這座城市有多少顆龍珠,a龍珠被移動了多少次

            思路:看懂題意后就知道用并查集了。詢問的前兩個問題都很好解決,有點難度的是第三個問題,龍珠被移動的次數。我用count數組統計每顆龍珠移動的次數,路徑壓縮后,每顆龍珠的父親就是它所在的城市,如果這顆龍珠所在的城市所有的龍珠被移走的話,這座城市變成一座空城市,所以不會有龍珠再被移動到這座城市,就是說一座城市只能轉移一次,假設a所在的城市的所有龍珠移動到了b,合并的時候統計這座城市移動的次數,那么統計龍珠的時候,只要統計它的父親它的祖父一直到它的老祖,每個長輩的count和就是這顆龍珠的移動次數。所以在Union的時候讓它父親的count++,Find的時候讓它遍歷到根節點每次都加上一個長輩的count。寫完后會感覺到,就是一個裸體的并查集。
            #include <iostream>
            #include 
            <cstdio>
            #include 
            <cstring>
            using namespace std;

            const int MAXN=10003;
            int father[MAXN],sum[MAXN],count[MAXN];
            void Init(int n)
            {
                
            for(int i=0;i<=n;i++)
                {
                    father[i]
            =i;
                    sum[i]
            =1;
                    count[i]
            =0;
                }
            }

            int Find(int x)
            {
                
            int temp;
                
            if(x==father[x]) return x;
                
            else
                {
                    temp
            =father[x];
                    father[x]
            =Find(father[x]);
                    count[x]
            +=count[temp];
                }
                
            return father[x];
            }

            void Union(int a,int b)
            {
                
            int x=Find(a);
                
            int y=Find(b);
                
            if(x==y) return;
                
            else
                {
                    father[x]
            =y;
                    count[x]
            ++;
                    sum[y]
            +=sum[x];
                    sum[x]
            =0;
                }
            }

            int main()
            {
                
            //freopen("input","r",stdin);
                
            //freopen("out","w",stdout);
                int t,cnt=1;
                scanf(
            "%d",&t);
                
            while(t--)
                {
                    
            int m,n;
                    scanf(
            "%d%d",&m,&n);
                    printf(
            "Case %d:\n",cnt++);
                    Init(m);
                    
            while(n--)
                    {
                        
            char s1;
                        getchar();
                        scanf(
            "%c",&s1);


                        
            if(s1=='T')
                        {
                            
            int a,b;
                            scanf(
            "%d%d",&a,&b);
                            Union(a,b);

                        }
                        
            else
                        {
                            
            int p;
                            scanf(
            "%d",&p);
                            
            int temp=Find(p);
                            printf(
            "%d %d %d\n",temp,sum[temp],count[p]);
                        }
                    }

                }


                
            return 0;
            }
                    
            久久久久久久精品成人热色戒| www.久久热.com| 一本大道久久香蕉成人网| 亚洲精品无码久久毛片| 97久久国产综合精品女不卡 | 66精品综合久久久久久久| 久久久久久国产精品无码下载| 无码人妻久久一区二区三区蜜桃| 午夜欧美精品久久久久久久| 99久久99久久精品国产| 久久99久国产麻精品66| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 久久国产乱子伦免费精品| 久久激情亚洲精品无码?V| 亚洲AV无码成人网站久久精品大| 久久精品中文字幕一区| 国产亚洲色婷婷久久99精品| 亚洲日韩欧美一区久久久久我| 国产91久久精品一区二区| 日韩精品无码久久久久久| 久久精品国产99国产精品| 久久久九九有精品国产| 欧美牲交A欧牲交aⅴ久久| 久久综合久久综合亚洲| 无码任你躁久久久久久| 国产精品免费久久久久久久久| 久久久久亚洲av无码专区喷水| 久久99国产精品久久99小说| 久久久久亚洲精品无码网址 | 久久九九有精品国产23百花影院| 日韩人妻无码精品久久免费一| 尹人香蕉久久99天天拍| 青青热久久国产久精品| 日本国产精品久久| 久久有码中文字幕| 国产精品久久久久久久app| 亚洲国产精品无码久久青草| 亚洲国产精品综合久久网络| 欧美色综合久久久久久| 午夜精品久久久久| 亚洲伊人久久大香线蕉综合图片|