• <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>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku 1182
		
            
		
             2009年7月12日 星期日

            題目鏈接：PKU 1182 食物鏈
             
            分類：并查集的拓展（經典）


            題目分析與算法模型

                    本題是一道經典的并查集的拓展，其中比較一般的解法是設立三個group，因為一共有三種動物。但其實有一種更加簡便的方法，具體如下，利用向量的思考模式將三個group合并成一個并查集，同時對每個節點保持其到根結點的相對類別偏移量，定義為：
            0——同類；
            1——食物；
            2——天敵；
            對于樹中的每一個節點（動物），記錄其與根節點的相對偏移量，即上面的0，1和2，這樣就可以根據相對平移量計算出其和根節點所代表的動物的關系，合并節點時，注意兩棵樹的根節點之間的相對偏移量，這里有幾個公式需要自己推導，都在代碼中了；

            Code：

             1            #include<stdio.h>
             2#define max 50005
             3
             4int n,k,i,j,parent[max],kind[max],count,a,b,d;
             5
             6void init(int n)
             7{
             8    for(j=1;j<=n;j++)
             9    {
            10        parent[j]=-1;
            11        kind[j]=0;
            12    }
            13}
            14int find(int x)
            15{
            16    int t=parent[x];
            17    if(t<0)return x;
            18    parent[x]=find(t);
            19    kind[x]=(kind[x]+kind[t])%3;
            20    return parent[x];
            21}
            22void Union(int x,int y,int d)
            23{
            24    if(x>n||y>n)count++;
            25    else if(d==1)
            26    {
            27        int root1=find(x),root2=find(y);
            28        if(root1==root2)
            29        {
            30            if(kind[x]!=kind[y])count++;
            31        }
            32        else
            33        {
            34            if(parent[root1]<parent[root2])   //root1為根
            35            {
            36                parent[root1]+=parent[root2];
            37                parent[root2]=root1;
            38                kind[root2]=(kind[x]-kind[y]+3)%3;       //需要自己推導
            39            }
            40            else                              //root2為根
            41            {
            42                parent[root2]+=parent[root1];
            43                parent[root1]=root2;
            44                kind[root1]=(kind[y]-kind[x]+3)%3;
            45            }
            46        }
            47    }
            48    else   //d=2
            49    {
            50        if(x==y)count++;
            51        else
            52        {
            53            int root1=find(x),root2=find(y);
            54            if(root1==root2)
            55            {
            56                if(kind[x]!=(kind[y]+1)%3)count++;  //需要自己推導
            57            }
            58            else
            59            {
            60                if(parent[root1]<parent[root2])   //root1為根
            61                {
            62                    parent[root1]+=parent[root2];
            63                    parent[root2]=root1;
            64                    kind[root2]=(kind[x]-kind[y]+5)%3;       //需要自己推導
            65                }
            66                else                              //root2為根
            67                { 
            68                    parent[root2]+=parent[root1];
            69                    parent[root1]=root2;
            70                    kind[root1]=(kind[y]-kind[x]+4)%3;      //需要自己推導
            71                }
            72            }
            73        }
            74    }
            75}
            76int main()
            77{
            78    scanf("%d%d",&n,&k);
            79    init(n);
            80    count=0;
            81    for(i=0;i<k;i++)
            82    {
            83        scanf("%d%d%d",&d,&a,&b);
            84        Union(a,b,d);
            85    }
            86    printf("%d\n",count);
            87    return 0;
            88}
            89
            

		
            
			posted on 2009-07-13 00:08 蝸牛也Coding 閱讀(1192) 評論(3)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: pku 1182[未登錄]
					
						2009-12-17 12:12
					
				YY
			
            
			
            
				YTE   回復  更多評論
				  
			
            
		
			
            
				# re: pku 1182
					
						2010-02-12 16:04
					
				Y
			
            
			
            
				大家注意了，那個1代表根是這個節點的食物，別誤解了  回復  更多評論
				  
			
            
		
			
            
				# re: pku 1182[未登錄]
					
						2010-03-26 19:15
					
				菜鳥
			
            
			
            
				可以簡單說一下這幾條語句什么意思么？

            kind[x]=(kind[x]+kind[t])%3;

            kind[root2]=(kind[x]-kind[y]+3)%3;

            kind[root2]=(kind[x]-kind[y]+5)%3;

              回復  更多評論
				  
			
            
		

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



国产精品视频久久久|
狠狠88综合久久久久综合网|
精品999久久久久久中文字幕|
久久久久久久综合狠狠综合|
久久久久久久精品妇女99|
久久久久亚洲av无码专区导航|
久久成人国产精品|
99久久精品免费看国产一区二区三区|
亚洲国产精品一区二区久久|
伊人久久大香线蕉综合5g|
婷婷伊人久久大香线蕉AV|
国产精品无码久久综合|
亚洲成av人片不卡无码久久|
好久久免费视频高清|
伊人色综合久久天天网|
久久夜色tv网站|
香蕉久久av一区二区三区|
久久国产视频网|
免费观看久久精彩视频|
亚洲第一极品精品无码久久|
久久精品无码一区二区app|
久久精品国产99久久久
|
亚洲成av人片不卡无码久久|
996久久国产精品线观看|
久久国产劲爆AV内射—百度|
思思久久99热免费精品6|
久久精品国产精品亚洲下载|
99精品久久精品一区二区|
欧美日韩久久中文字幕|
久久综合成人网|
久久免费精品视频|
97精品伊人久久大香线蕉app|
久久免费观看视频|
看全色黄大色大片免费久久久|
青青国产成人久久91网|
久久99热这里只有精品国产|
中文字幕一区二区三区久久网站|
WWW婷婷AV久久久影片|
色综合久久中文字幕无码|
久久精品亚洲AV久久久无码|
亚洲精品视频久久久|