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



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



伊人久久精品影院|
日韩中文久久|
狠狠狠色丁香婷婷综合久久五月|
狠狠色丁香久久综合婷婷|
久久精品成人欧美大片|
亚洲AV日韩AV天堂久久|
精品久久久久久久久久久久久久久|
思思久久好好热精品国产|
国产午夜免费高清久久影院|
青青草原综合久久大伊人导航|
国内精品久久人妻互换|
国产免费久久精品99re丫y|
欧美大香线蕉线伊人久久|
久久久久久久综合综合狠狠|
久久er99热精品一区二区|
亚洲精品久久久www|
国产视频久久|
国产一区二区三区久久|
久久久久亚洲av无码专区喷水|
久久久久久极精品久久久
|
久久www免费人成精品香蕉|
伊人久久大香线蕉av不卡|
久久这里有精品视频|
亚洲国产成人久久精品影视|
乱亲女H秽乱长久久久|
久久中文字幕人妻丝袜|
一本综合久久国产二区|
色综合久久88色综合天天 |
国产成人精品综合久久久|
久久国产精品久久|
国产精品久久久久影院嫩草|
精品国产VA久久久久久久冰
|
蜜臀av性久久久久蜜臀aⅴ|
偷偷做久久久久网站|
一日本道伊人久久综合影|
久久影院亚洲一区|
中文字幕久久精品|
97精品伊人久久久大香线蕉|
久久亚洲AV无码精品色午夜|
久久久久亚洲国产|
欧美黑人激情性久久|