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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2011年1月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導航
            

					

            統計
            
	
					

            公告
            
	
            統計系統
            

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



99久久777色|
综合久久精品色|
久久久国产精华液|
久久久久亚洲av成人网人人软件|
久久久精品国产sm调教网站|
a级毛片无码兔费真人久久|
尹人香蕉久久99天天拍|
久久91精品久久91综合|
久久无码国产专区精品|
93精91精品国产综合久久香蕉|
亚洲中文久久精品无码|
久久一区二区三区99|
97精品国产97久久久久久免费|
无码国内精品久久人妻|
一本久久a久久精品综合香蕉|
国产高潮国产高潮久久久91|
久久不见久久见免费视频7|
超级97碰碰碰碰久久久久最新|
精品多毛少妇人妻AV免费久久|
97r久久精品国产99国产精|
久久精品人妻中文系列|
亚洲伊人久久成综合人影院|
精品久久久久久久中文字幕|
亚洲综合久久综合激情久久|
久久超碰97人人做人人爱|
亚洲AV无码久久精品成人|
人人妻久久人人澡人人爽人人精品|
久久国产精品一区|
久久se这里只有精品|
久久久久久极精品久久久|
久久久精品无码专区不卡|
久久精品国产国产精品四凭|
精品国产乱码久久久久久浪潮
|
国产一区二区精品久久凹凸
|
久久久久一区二区三区|
久久久久久毛片免费播放|
国产精品一久久香蕉国产线看观看
|
久久久久亚洲AV无码麻豆|
久久夜色精品国产噜噜噜亚洲AV
|
亚洲一区精品伊人久久伊人|
久久天天躁狠狠躁夜夜不卡|