2010年02月07日星期日.sgu190
sgu190:
一開始想到的竟然是狀態壓縮dp，然后一看n，貌似大了點。
然后怎么想也沒思路，上網看看,才知道原來二分圖還可以這么用，我怎么從來也沒想到呢。。。。
將圖像國際象棋棋盤那樣黑白染色，然后給對于每個顏色給每個格子一個編號。
然后選一個染色，對每個格子和他旁邊的格子建邊，這樣構成一個二分圖。
求出最大的匹配數，然后再按照題目的猥瑣要求輸出即可。
注意 題目中棋盤的格式是這個樣子的。
(2,1) (2,2)
(1,1) (1,2)
左下角是(1,1)
如果按照平常的左上角是(1,1)來搞，需要注意一下輸出
1
2 int g[801][801],n,P;
3 const int BLACK = 1;
4 const int WHITE = 2;
5 const int REMOVED = 3;
6 int num[41][41],bsp,wsp,cnt;
7 int board[41][41];
8 int bcoord[41*41][2];
9 int wcoord[41*41][2];
10 int vis[801];
11 int L[801],R[801];
12
13 bool make_graph()
14 {
15 int i,j;cnt = 0;
16 for (i = 1;i <= n;i++) {
17 for (j = 1;j <= n;j++) {
18 if (board[i][j] != REMOVED) {
19 cnt ++;
20 if ((i+j)%2==1) {
21 board[i][j] = WHITE;
22 wcoord[wsp][0] = i, wcoord[wsp][1] = j;
23 num[i][j] = wsp++;
24 }else {
25 board[i][j] = BLACK;
26 bcoord[bsp][0] = i, bcoord[bsp][1] = j;
27 num[i][j] = bsp++;
28 }
29 }
30 }
31 }
32 for (i = 1;i <= n;i++) {
33 for (j = 1;j <= n;j++) {
34 if (board[i][j] == BLACK) {
35 if (board[i+1][j] == WHITE) g[num[i][j]][num[i+1][j]] = 1;
36 if (board[i][j+1] == WHITE) g[num[i][j]][num[i][j+1]] = 1;
37 if (board[i-1][j] == WHITE) g[num[i][j]][num[i-1][j]] = 1;
38 if (board[i][j-1] == WHITE) g[num[i][j]][num[i][j-1]] = 1;
39 }
40 }
41 }
42 return true;
43 }
44
45 bool dfs(int u) {
46 for (int v = 0;v < wsp;v++) {
47 if (g[u][v] && !vis[v]) {
48 vis[v] = true;
49 if (R[v] == -1 || dfs(R[v])) {
50 L[u] = v;
51 R[v] = u;
52 return true;
53 }
54 }
55 }
56 return false;
57 }
58
59 int MaxMatch()
60 {
61 int i,res = 0;
62 memset(L,-1,sizeof(L));
63 memset(R,-1,sizeof(R));
64
65 for (i = 0;i < bsp;i++) {
66 if (L[i] == -1) {
67 memset(vis,0,sizeof(vis));
68 if (dfs(i)) {
69 res++;
70 }
71 }
72 }
73 return res;
74 }
75
76 int out[801][2],top;
77 bool proc()
78 {
79 make_graph(); if (cnt & 1) { return false; }
80 if (bsp == 0 || wsp == 0) { return false; }
81 if (bsp != wsp) { return false; }
82 return (MaxMatch() * 2 == cnt);
83 }
84
85 int main()
86 {
87 int i,j,k,a,b;
88 scanf("%d%d",&n,&P);
89 for (i = 0;i < P;i++) {
90 scanf("%d%d",&a,&b);
91 board[a][b] = REMOVED;
92 }
93 if (proc()) {
94 printf("Yes\n");
95 top = 0;
96 for (i = 0;i < bsp;i++) {
97 if (bcoord[i][1] == wcoord[L[i]][1]) {
98 if (bcoord[i][0] < wcoord[L[i]][0]) {
99 out[top][0] = bcoord[i][0];
100 out[top][1] = bcoord[i][1];
101 top++;
102 }else {
103 out[top][0] = wcoord[L[i]][0];
104 out[top][1] = wcoord[L[i]][1];
105 top++;
106 }
107 }
108 }
109
110 printf("%d\n",top);
111 for (i = 0;i < top;i++) { printf("%d %d\n",out[i][0],out[i][1]); }
112
113 top = 0;
114 for (i = 0;i < bsp;i++) {
115 if (bcoord[i][0] == wcoord[L[i]][0]) {
116 if (bcoord[i][1] < wcoord[L[i]][1]) {
117 out[top][0] = bcoord[i][0];
118 out[top][1] = bcoord[i][1];
119 top++;
120 }else {
121 out[top][0] = wcoord[L[i]][0];
122 out[top][1] = wcoord[L[i]][1];
123 top++;
124 }
125 }
126 }//http://www.shnenglu.com/schindlerlee
127 printf("%d\n",top);
128 for (i = 0;i < top;i++) { printf("%d %d\n",out[i][0],out[i][1]); }
129 }else {
130 printf("No\n");
131 }
132
133
134 return 0;
135 }
136
137