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



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



少妇人妻综合久久中文字幕|
久久91精品国产91久久户|
久久久噜噜噜久久|
久久久精品人妻一区二区三区蜜桃
|
亚洲午夜无码久久久久|
久久99精品国产99久久|
久久男人AV资源网站|
久久综合给久久狠狠97色|
亚洲午夜精品久久久久久人妖|
久久久久久国产精品无码下载|
久久免费视频网站|
亚洲精品乱码久久久久久蜜桃图片
|
久久免费的精品国产V∧|
久久久久亚洲AV成人网人人网站|
久久无码AV一区二区三区|
久久免费视频观看|
人妻精品久久久久中文字幕69|
久久久久人妻一区精品果冻|
久久国产精品一区二区|
久久久久se色偷偷亚洲精品av|
理论片午午伦夜理片久久|
国产精品久久久久久久久鸭|
色综合久久久久综合体桃花网|
欧洲国产伦久久久久久久|
91精品国产91久久久久久|
91久久精一区二区三区大全|
国内精品久久久久影院薰衣草
|
久久国产精品成人片免费|
久久久久久久久波多野高潮|
欧美一级久久久久久久大|
久久精品国产99久久久香蕉|
久久精品国内一区二区三区|
韩国免费A级毛片久久|
久久久久久久久久久久中文字幕|
久久久久高潮综合影院|
少妇人妻综合久久中文字幕|
亚洲国产欧洲综合997久久|
无码久久精品国产亚洲Av影片|
久久亚洲私人国产精品vA|
久久亚洲精精品中文字幕|
久久精品国产亚洲av水果派
|