• <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>
            posts - 101,  comments - 57,  trackbacks - 0
                   這是一題相當有水平的并查集問題。雖然我一次性ac,但是基本上是沒有任何思路搜索了一下牛人思路才過的。

                   思考這題時,我陷入到了以下怪圈:
            1.并查集應該是無限的,但是貌似這題的并集只有三個
            2.當兩者關系未被確認是哪個集合時,會出現無限多的臨時子集
            3.如何表示臨時子集
              
                   看了看牛人的思路,相當巧妙:并查集基本還是無限集,有限集用關系向量來表示。
            1.使用關系向量的方法,讓我獲益匪淺。
            2.計算關系向量的方法,又如此的巧合。
            3.并查集并不一定是相同的才并一起,又回歸到第一點,當關系向量可以用有限集表示時,并查集里的元素可以不是同一類元素。

            最后還要說,這題相當牛B.
            #include "stdio.h"

            #define MAX 50001

            #define Similar 0   
            #define Enemy   1
            #define Food    2
            //  Food eat Enemy
            //  Enemy eat Similar
            //  Similar eat Food

            struct _xtree
            {
                
            int parent;
                
            int relation;
            }
            xtree[MAX];

            int N, K;

            void build()
            {
                
            int i;
                
            for (i = 1; i <= N; i++)
                
            {
                    xtree[i].parent   
            = i;
                    xtree[i].relation 
            = Similar;
                }

            }


            int find(int i)
            {
                
            int p = xtree[i].parent;
                
            if (p != i)
                
            {
                    xtree[i].parent   
            = find(xtree[i].parent);
                    xtree[i].relation 
            = (xtree[p].relation + xtree[i].relation) % 3;
                }


                
            return xtree[i].parent;
            }


            int check(int x, int y, int r)
            {
                
            int root_x, root_y, root_r;

                
            if (x > N || y > N)
                
            {
                    
            return 0;
                }


                root_x 
            = find(x);
                root_y 
            = find(y);
                
                
            if (root_x == root_y)  // x relate y
                {        
                    
            return (xtree[x].relation - xtree[y].relation + 3% 3  == r ? 1 : 0;          
                }

                
            else
                
            {
                    root_r 
            =  (xtree[y].relation + r + (3 - xtree[x].relation)) % 3;
                    xtree[root_x].parent   
            = root_y;
                    xtree[root_x].relation 
            = root_r;
                    
            return 1;
                }

            }


            void main()
            {
                
            int op, x, y;
                
            int count = 0;

                scanf(
            "%d %d"&N, &K);

                build();

                
            while (K--)
                
            {
                    scanf(
            "%d %d %d"&op, &x, &y);
                   
                    
            if (!check(x, y, op == 1 ? Similar : Enemy))
                    
            {
                        count
            ++;
                    }
                        
                }

                printf(
            "%d\n", count);
            }


            posted on 2010-08-28 21:11 margin 閱讀(165) 評論(0)  編輯 收藏 引用
            <2008年10月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿

            隨筆檔案

            文章分類

            文章檔案

            收藏夾

            常去的壇子

            • CVC電腦病毒論壇
            • 很多人說我是AV,我告訴他們:別瞧不起人,我們也能創造價值
            • 安全焦點
            • 黑客聚集的地方,一般是好酒最多的地方...
            • 看雪論壇
            • 國內最強的加密解密論壇,成醉其中經常夜不歸宿
            • 驅動開發論壇
            • 厭倦了啤的朋友們,來我們來整點白的...痛痛快快的BSOD也好過隔鞋瘙癢!

            我的朋友

            • Sen的blog
            • IDE方面資深的受害者...經常為一個變量的定義找不著北的痛苦程序員(深表同情)
            • 老羅的blog
            • 良師益友,千年水牛,引擎猛男,分析怪獸,墨鏡酷哥,臺球高手....

            搜索

            •  

            最新評論

            久久er国产精品免费观看8| 一本久道久久综合狠狠躁AV| 日本久久中文字幕| 欧美久久久久久精选9999| 99久久精品无码一区二区毛片| 亚洲综合婷婷久久| 婷婷久久综合九色综合绿巨人| 久久精品成人欧美大片 | 久久久精品国产免大香伊 | 久久人爽人人爽人人片AV| 久久久久亚洲精品日久生情| 国内精品伊人久久久久网站| 青青国产成人久久91网| 亚洲精品成人久久久| AV无码久久久久不卡蜜桃| 国产免费久久精品丫丫| 亚洲精品无码久久久影院相关影片| 久久A级毛片免费观看| 久久这里只精品99re66| 免费一级欧美大片久久网| 久久综合九色综合欧美狠狠| 亚洲精品无码久久久久sm| 久久人人爽人人爽人人片AV不 | 国产精品国色综合久久| 久久AAAA片一区二区| 中文精品99久久国产| 亚洲欧美另类日本久久国产真实乱对白| 狠色狠色狠狠色综合久久| 国产一区二区三区久久精品| 国产精品免费看久久久| 国内精品久久国产大陆| 欧美国产成人久久精品| 香港aa三级久久三级老师2021国产三级精品三级在| 老色鬼久久亚洲AV综合| 久久露脸国产精品| 久久综合狠狠综合久久综合88| 88久久精品无码一区二区毛片| 亚州日韩精品专区久久久| 69久久精品无码一区二区| 久久国产精品无| 99久久精品免费国产大片|