• <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 閱讀(1202) 評論(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年8月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



色婷婷久久久SWAG精品|
国产亚洲精品自在久久|
亚洲国产日韩欧美久久|
欧美一区二区久久精品|
性欧美丰满熟妇XXXX性久久久
|
亚洲а∨天堂久久精品9966|
一本久久精品一区二区|
MM131亚洲国产美女久久|
久久九色综合九色99伊人|
久久青青草原亚洲av无码app
|
精品久久人人爽天天玩人人妻
|
久久午夜综合久久|
久久精品人人做人人妻人人玩|
国产 亚洲 欧美 另类 久久|
人妻久久久一区二区三区|
久久亚洲电影|
观看 国产综合久久久久鬼色 欧美 亚洲 一区二区
|
亚洲国产精品久久66|
久久青青草原亚洲av无码app|
模特私拍国产精品久久|
91久久精品国产成人久久|
99久久成人国产精品免费|
午夜精品久久久久久中宇|
2021最新久久久视精品爱|
久久久久综合中文字幕|
精品久久人人爽天天玩人人妻|
国产Av激情久久无码天堂|
97精品国产97久久久久久免费|
久久综合久久性久99毛片|
久久久精品波多野结衣|
精品久久综合1区2区3区激情|
国产福利电影一区二区三区久久久久成人精品综合
|
亚洲精品tv久久久久|
久久久久人妻一区精品|
久久国产免费|
欧美成a人片免费看久久|
青青热久久国产久精品|
人人妻久久人人澡人人爽人人精品|
久久这里的只有是精品23|
国产偷久久久精品专区|
无码人妻久久一区二区三区免费|