• <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的棋盤，每次可以將棋盤的一行或者一列染成一種顏色，現在給出棋盤的末狀態，請給出一種染色的方案，并且要求字典序最小
            

            Summary
            

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

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

             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 閱讀(182) 評論(0)  編輯 收藏 引用  所屬分類: graph 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

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

            

					

            導航
            

					

            統計
            
	
					

            公告
            
	
            統計系統
            

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久乐国产精品亚洲综合|
好属妞这里只有精品久久|
久久久久国色AV免费观看|
久久久WWW成人免费精品|
中文字幕亚洲综合久久菠萝蜜|
一本色综合久久|
99麻豆久久久国产精品免费|
久久国产精品二国产精品|
久久久久久久97|
国产日韩欧美久久|
日韩精品久久久久久久电影蜜臀|
日本三级久久网|
日韩乱码人妻无码中文字幕久久|
狠狠精品干练久久久无码中文字幕|
亚洲日韩欧美一区久久久久我|
99久久综合狠狠综合久久止|
久久亚洲熟女cc98cm|
亚洲国产天堂久久综合网站|
亚洲av日韩精品久久久久久a|
久久99精品国产麻豆蜜芽|
亚洲国产精品无码久久一区二区|
久久97久久97精品免视看|
a高清免费毛片久久|
伊人久久大香线蕉av一区|
久久精品中文字幕有码|
久久亚洲国产中v天仙www|
久久精品国产亚洲AV麻豆网站|
欧美黑人激情性久久|
亚洲国产天堂久久综合|
欧美日韩精品久久久久|
伊人色综合久久天天|
久久亚洲国产欧洲精品一|
午夜不卡888久久|
国产精品美女久久久久网|
久久人人爽人人爽人人AV东京热
|
久久国产欧美日韩精品|
久久天天躁夜夜躁狠狠|
丁香五月综合久久激情|
一本大道加勒比久久综合|
欧美一区二区精品久久|
99精品伊人久久久大香线蕉|