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

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			PKU3853 Painting 拓撲排序
		
            
		
            題意大概是這樣，有一個n*n的棋盤，每次可以將棋盤的一行或者一列染成一種顏色，現(xiàn)在給出棋盤的末狀態(tài)，請給出一種染色的方案，并且要求字典序最小
            

            Summary
            

            可以使用類似拓撲排序的方法處理這個問題。對于每種顏色，有三種可能：可以判斷橫放，可以判斷豎放，不可判斷。之后不斷選出一個在最上面顏色，刪去（也就是設置為0）。判斷最上面的要求是：該顏色在該行的數(shù)目，加上已經(jīng)被刪去（也就是0）的方格，等于列的數(shù)目；或該顏色在該列的數(shù)目，加上已經(jīng)被刪去（也就是0）的方格，等于行的數(shù)目。 
            

            注意字典序的處理。因為我們是逆序得到答案的。拓撲排序中，要逆序得到字典序最大，才能得到正序的字典序最小
            

             1# include <iostream>
             2# include <set>
             3# include <stack>
             4using namespace std;
             5int map[101][101];
             6int n,m;
             7bool selectrow(int pos,int num)
             8{
             9   for(int i=0;i<m;i++)
            10     if(map[pos][i]!=-1&&map[pos][i]!=num) return false;
            11   for(int i=0;i<n;i++)
            12       if(i!=pos)
            13           for(int j=0;j<m;j++)
            14               if(map[i][j]==num)
            15                   return false;
            16   return true;
            17}
            18bool selectcol(int pos,int num)
            19{
            20   for(int i=0;i<n;i++)
            21     if(map[i][pos]!=-1&&map[i][pos]!=num) return false;
            22   for(int j=0;j<m;j++)
            23       if(j!=pos)
            24           for(int i=0;i<n;i++)
            25               if(map[i][j]==num)
            26                   return false;
            27   return true;
            28}
            29int main()
            30{
            31    while(true)
            32    {
            33       cin>>n>>m;
            34       set<int,greater<int> > refer;
            35       if(!n&&!m) break;
            36       for(int i=0;i<n;i++)
            37         for(int j=0;j<m;j++)
            38         {
            39           cin>>map[i][j];
            40           refer.insert(map[i][j]);
            41         }
            42       
            43       stack<int> ans;
            44       while(!refer.empty())
            45       {
            46         // if(emptymap()) break;
            47          for(set<int,greater<int> >::iterator p=refer.begin();p!=refer.end();p++)
            48          {
            49             for(int i=0;i<n;i++)
            50               for(int j=0;j<m;j++)
            51                  if(map[i][j]==(*p))
            52                  {
            53                     if(selectrow(i,*p))
            54                     {
            55                       for(int k=0;k<m;k++)
            56                       {
            57                          map[i][k]=-1;
            58                       }
            59                       ans.push(*p);
            60                       refer.erase(p);
            61                       goto end;
            62                     }
            63                     else if(selectcol(j,*p))
            64                     {
            65                       for(int k=0;k<n;k++)
            66                         map[k][j]=-1;
            67                       ans.push(*p);
            68                       refer.erase(p);
            69                       goto end;
            70                     }
            71                  }
            72          }
            73          end:;
            74       }
            75       while(!refer.empty())
            76       {
            77          ans.push(*refer.begin());
            78          refer.erase(refer.begin());
            79       }
            80       cout<<ans.top();
            81       ans.pop();
            82       while(!ans.empty())
            83       {
            84         cout<<" "<<ans.top();
            85         ans.pop();
            86       }
            87       cout<<endl;
            88    }
            89    return 0;
            90}
            91
            92
            

		
            
			posted on 2010-10-14 19:19 yzhw 閱讀(177) 評論(0)  編輯 收藏 引用  所屬分類: graph 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年10月>
            
	
            日一二三四五六
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            

            

					

            導航
            

					

            統(tǒng)計
            
	
					

            公告
            
	
            統(tǒng)計系統(tǒng)
            

					

            留言簿(1)
            


		
            隨筆分類(227)
            
		
				
			
	
		
            文章分類(2)
            
		
				
			
	
		
            OJ
            
		
				
			
	


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久久久精品免费看SSS|
2022年国产精品久久久久|
久久99国产亚洲高清观看首页
|
国产产无码乱码精品久久鸭|
久久这里的只有是精品23|
久久久精品国产亚洲成人满18免费网站
|
精品伊人久久大线蕉色首页|
婷婷久久综合九色综合绿巨人|
久久亚洲高清观看|
久久精品国产秦先生|
久久99精品久久久久久
|
99久久er这里只有精品18|
中文字幕乱码人妻无码久久|
久久久噜噜噜久久中文字幕色伊伊|
亚洲人AV永久一区二区三区久久|
热RE99久久精品国产66热|
午夜精品久久久久久影视777|
亚洲国产天堂久久久久久|
三级三级久久三级久久|
亚洲va久久久噜噜噜久久天堂|
人妻精品久久无码区|
日韩一区二区久久久久久|
亚洲午夜精品久久久久久人妖|
久久国产午夜精品一区二区三区|
久久久噜噜噜久久|
久久久久久久97|
狠狠色噜噜狠狠狠狠狠色综合久久
|
99精品国产99久久久久久97
|
99久久夜色精品国产网站|
久久久人妻精品无码一区
|
2021国内精品久久久久久影院|
色欲综合久久躁天天躁蜜桃|
久久精品免费观看|
天天做夜夜做久久做狠狠|
久久久久久国产精品免费无码|
99久久精品这里只有精品|
久久精品国产色蜜蜜麻豆|
99久久综合狠狠综合久久|
2021国产精品久久精品|
嫩草影院久久99|
久久天天躁夜夜躁狠狠躁2022
|