二分圖匹配的巧妙應(yīng)用相當(dāng)巧妙!CTU 2005 Openhttp://acm.pku.edu.cn/JudgeOnline/problem?id=2990題意:8*8的棋盤(pán), 初始放置2個(gè)相同的棋子. Alice和Bob輪流行動(dòng). 每次行動(dòng)可以把其中一個(gè)棋子移到它上下左右相鄰格內(nèi)(某些格子壞掉了,則不能移). 當(dāng)某人的移動(dòng)使兩棋子重合時(shí), 他贏. 另, 一局中不能出現(xiàn)重復(fù)的局面. 比如(0,0)(4,0) -> (1,0)(4,0)合法, 此時(shí)如果再(1,0)(4,0) -> (0,0)(4,0)則非法. 當(dāng)一個(gè)人無(wú)子可動(dòng)時(shí), 他輸.兩人都用最優(yōu)策略. 問(wèn)先手的Alice必勝還是必?cái)?解:把每個(gè)合法狀態(tài)看成一個(gè)頂點(diǎn), 則狀態(tài)轉(zhuǎn)移就是向其它點(diǎn)連邊. 這樣建的圖是二分圖.而兩人下棋, 就是在圖上以初始狀態(tài)的頂點(diǎn)為起點(diǎn), 沿邊移動(dòng). 由于建的圖是由所有合法狀態(tài)與合法移動(dòng)組成的, 因此, 移動(dòng)到哪個(gè)集合(A與B), 就表示輪到誰(shuí)行動(dòng). 當(dāng)無(wú)法再移動(dòng)時(shí), 點(diǎn)在哪個(gè)集合就表示對(duì)應(yīng)的人輸了.狀態(tài)不重復(fù)出現(xiàn), 表示移動(dòng)路徑?jīng)]有環(huán).誰(shuí)贏誰(shuí)輸, 與路徑長(zhǎng)度的奇偶性密切相關(guān).考慮二分圖的最大匹配, 也是個(gè)找交替路徑擴(kuò)張的過(guò)程.設(shè)起點(diǎn)為v, 分情況討論v的狀態(tài)與路徑長(zhǎng)度的關(guān)系: (1) v是自由點(diǎn). 這表示v的任意鄰接點(diǎn)vB都是浸潤(rùn)點(diǎn). 不管選哪個(gè)vB, 都可以沿著它的匹配邊走到vA'. 只要Bob每次都沿匹配邊走, 由于不可能達(dá)到另一個(gè)自由點(diǎn), 因此終點(diǎn)必屬于A, Bob必勝.(2) v是浸潤(rùn)點(diǎn), 此時(shí)v所在的交替路徑兩個(gè)端點(diǎn)分布情況可能有幾種: a)對(duì)所有交替路徑, 端點(diǎn)都在B集. 這時(shí)只要Alice每次都沿著匹配邊走, 必勝. b)存在一條交替路徑, 端點(diǎn)都在A集. 把沿v的匹配邊走的那一半全部置反, 就變成(1)的狀態(tài)了, 因此2者等價(jià). c)沿v的匹配邊走的那一半全終止于B, 另一半終止于A. 只要Alice一開(kāi)始就沿匹配邊走, 后面策略同a. 其它情形不可能在最大匹配中出現(xiàn), 故不討論. 這正是充分利用了最大匹配的性質(zhì).因此對(duì)本題先求最大匹配, 然后判斷是否為(1)或(2b), 即可知?jiǎng)儇?fù).代碼如下:
1 #include <iostream>
2 using namespace std;
3
4 const int MAX_VERT = (1<<12)+1;
5 const int MAX_EDGE = MAX_VERT * 16;
6 struct EDGE{
7 int v,e;
8 }edg[ MAX_EDGE ];
9 int se, gg[ MAX_VERT ], nv;
10 int start;
11 int mat[ MAX_VERT ];
12 bool ok[ MAX_VERT ], vis[ MAX_VERT ];
13
14 int N,M;
15 char bo[20][20];
16
17 bool chkpt(int x, int y)
18 {
19 if(x<0 || x>=M || y<0 || y>=N) return false;
20 if(bo[y][x]=='#') return false;
21 return true;
22 }
23
24 //判斷合法狀態(tài)
25 bool chksta(int x1, int y1, int x2, int y2)
26 {
27 if(!chkpt(x1,y1) || !chkpt(x2,y2)) return false;
28 if(abs(x1-x2)+abs(y1-y2)<=1) return false;
29 return true;
30 }
31
32 //位壓縮存狀態(tài)
33 int encode(int x1, int y1, int x2, int y2)
34 {
35 if(y1 > y2 || (y1==y2 && x1 > x2)) //小點(diǎn)放前面, 避免重復(fù)狀態(tài)
36 swap(y1,y2), swap(x1,x2);
37 int v = x1;
38 v = (v<<3) | y1;
39 v = (v<<3) | x2;
40 v = (v<<3) | y2;
41 return v;
42 }
43
44 inline void addedge(int u, int v)
45 {
46 edg[se].v = v;
47 edg[se].e = gg[u];
48 gg[u] = se++;
49 }
50
51 void addmove(int u, int x1, int y1, int x2, int y2)
52 {
53 if(!chksta(x1, y1, x2, y2)) return ;
54 int v = encode(x1, y1, x2, y2);
55 addedge(u, v);
56 }
57
58 //添加狀態(tài)轉(zhuǎn)移的邊
59 void gene(int x1, int y1, int x2, int y2)
60 {
61 if(!chksta(x1,y1,x2,y2)) return;
62 int u = encode(x1,y1,x2,y2);
63 ok[u] = true;
64 mat[u] = -1;
65 addmove(u, x1+1, y1, x2, y2);
66 addmove(u, x1-1, y1, x2, y2);
67 addmove(u, x1, y1+1, x2, y2);
68 addmove(u, x1, y1-1, x2, y2);
69 addmove(u, x1, y1, x2+1, y2);
70 addmove(u, x1, y1, x2-1, y2);
71 addmove(u, x1, y1, x2, y2+1);
72 addmove(u, x1, y1, x2, y2-1);
73 }
74
75 //建圖
76 void input()
77 {
78 int x1, y1, x2, y2;
79
80 for(y1=0; y1<N; y1++)
81 scanf("%s",bo[y1]);
82
83 se = 1;
84 memset(gg,0,sizeof(gg));
85 nv = M << 9;
86 memset(ok, false, sizeof(ok));
87 memset(mat, 0xff, sizeof(mat));
88 memset(vis, false, sizeof(vis));
89
90 int c=0, tx[2],ty[2];
91 for(y1=0; y1<N; y1++){
92 for(x1=0; x1<M; x1++){
93 if(bo[y1][x1] == 'P')
94 tx[c]=x1, ty[c]=y1, c++;
95 for(x2=x1+1; x2<M; x2++)
96 gene(x1,y1,x2,y1);
97 for(y2=y1+1; y2<N; y2++)
98 for(x2=0; x2<M; x2++)
99 gene(x1,y1,x2,y2);
100 }
101 }
102 start = encode(tx[0], ty[0], tx[1], ty[1]);
103 }
104
105 bool hungrey(int r)
106 {
107 //這個(gè)匹配函數(shù)不分XY集, 因此匹配點(diǎn)雙方的mat標(biāo)記都要修改
108 int i,j,k;
109 vis[r] = true;
110 for(j=gg[r]; j>0; j=edg[j].e){
111 int v = edg[j].v;
112 if(!vis[v]){
113 vis[v] = true;
114 if(mat[v]==-1 || hungrey(mat[v])){
115 mat[v] = r;
116 mat[r] = v;
117 return true;
118 }
119 }
120 }
121 return false;
122 }
123
124 int main()
125 {
126 int i,j,k;
127 while(scanf("%d %d",&N,&M)!=EOF){
128 input();
129 if( !ok[start] ){
130 puts("Alice wins.");
131 continue;
132 }
133
134 for(i=0; i<nv; i++){
135 memset(vis, false, sizeof(vis));
136 if( mat[i]==-1 ) hungrey(i);
137 }
138 if( mat[start]!=-1 ){ //判斷是否是(2b)并轉(zhuǎn)化為(1)
139 memset(vis, false, sizeof(vis));
140 vis[start] = true;
141 if(hungrey(mat[start]))
142 mat[start] = -1;
143 }
144
145 if( mat[start]!=-1 )
146 puts("Alice wins.");
147 else
148 puts("Bob wins.");
149 }
150 return 0;
151 }
152
posted on 2009-07-06 11:55
wolf5x 閱讀(380)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
acm_icpc