• <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 閱讀(1196) 評論(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)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



亚洲狠狠婷婷综合久久蜜芽|
青青青国产成人久久111网站|
久久久国产精品|
亚洲国产成人精品久久久国产成人一区二区三区综|
国产成人无码精品久久久久免费
|
久久久久久精品久久久久|
综合网日日天干夜夜久久|
国产精品久久久久久影院|
久久久久久噜噜精品免费直播|
思思久久99热只有频精品66|
国产午夜免费高清久久影院|
青青久久精品国产免费看|
久久精品人成免费|
亚洲国产综合久久天堂|
国产一级持黄大片99久久|
亚洲国产视频久久|
精品国产青草久久久久福利
|
97精品伊人久久大香线蕉app|
久久人妻少妇嫩草AV无码蜜桃|
久久久国产乱子伦精品作者|
亚洲一级Av无码毛片久久精品|
久久久久久免费一区二区三区|
久久久一本精品99久久精品66
|
久久亚洲欧洲国产综合|
久久精品国产亚洲av麻豆色欲|
亚洲综合久久夜AV |
久久亚洲中文字幕精品一区|
久久综合欧美成人|
久久综合九色综合欧美狠狠|
久久夜色精品国产噜噜噜亚洲AV|
亚洲欧美另类日本久久国产真实乱对白
|
久久久久亚洲av无码专区|
久久笫一福利免费导航|
久久国产成人|
久久99精品久久久久久9蜜桃|
九九久久99综合一区二区|
久久精品无码午夜福利理论片|
久久久久亚洲AV无码专区首JN|
2021最新久久久视精品爱|
久久青青草视频|
亚洲国产精品无码久久久不卡|