国产精品久久亚洲7777,欧美激情亚洲另类,亚洲一区二区在线观看视频

江蘇大學

PKU3853 Painting 拓撲排序

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

Summary

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

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

1

# include <iostream>
2

# include <set>
3

# include <stack>
4

using namespace std;
5

int map[101][101];
6

int n,m;
7

bool 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

}
18

bool 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

}
29

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

只有注冊用戶登錄后才能發表評論。


相關文章: pku3905 2-SAT問題 &我對2-SAT問題的最新理解 The 36th ACM/ICPC Asia Regional Dalian Online Contest 大連2011ICPC網絡賽個人題解 pku2135 Farm Tour 經典最小費用流 pku 2132 Cow Math BFS pku3686 The Windy's 匹配好題！ pku2400 Supervisor, Supervisee 二分圖最優匹配的全部解 pku1202 Family DAG圖上的概率DP pku1944 Fiber Communications 圖論好題！總體上的觀察，算法不難 pku1894-1903 Northeastern Europe 2003 解題報告 pku2902 Intercepting Missiles 線段樹+離散化+二分圖匹配，注意C++短路

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理