二分圖匹配的巧妙應用相當巧妙!CTU 2005 Openhttp://acm.pku.edu.cn/JudgeOnline/problem?id=2990題意:8*8的棋盤, 初始放置2個相同的棋子. Alice和Bob輪流行動. 每次行動可以把其中一個棋子移到它上下左右相鄰格內(某些格子壞掉了,則不能移). 當某人的移動使兩棋子重合時, 他贏. 另, 一局中不能出現重復的局面. 比如(0,0)(4,0) -> (1,0)(4,0)合法, 此時如果再(1,0)(4,0) -> (0,0)(4,0)則非法. 當一個人無子可動時, 他輸.兩人都用最優策略. 問先手的Alice必勝還是必敗?解:把每個合法狀態看成一個頂點, 則狀態轉移就是向其它點連邊. 這樣建的圖是二分圖.而兩人下棋, 就是在圖上以初始狀態的頂點為起點, 沿邊移動. 由于建的圖是由所有合法狀態與合法移動組成的, 因此, 移動到哪個集合(A與B), 就表示輪到誰行動. 當無法再移動時, 點在哪個集合就表示對應的人輸了.狀態不重復出現, 表示移動路徑沒有環.誰贏誰輸, 與路徑長度的奇偶性密切相關.考慮二分圖的最大匹配, 也是個找交替路徑擴張的過程.設起點為v, 分情況討論v的狀態與路徑長度的關系: (1) v是自由點. 這表示v的任意鄰接點vB都是浸潤點. 不管選哪個vB, 都可以沿著它的匹配邊走到vA'. 只要Bob每次都沿匹配邊走, 由于不可能達到另一個自由點, 因此終點必屬于A, Bob必勝.(2) v是浸潤點, 此時v所在的交替路徑兩個端點分布情況可能有幾種: a)對所有交替路徑, 端點都在B集. 這時只要Alice每次都沿著匹配邊走, 必勝. b)存在一條交替路徑, 端點都在A集. 把沿v的匹配邊走的那一半全部置反, 就變成(1)的狀態了, 因此2者等價. c)沿v的匹配邊走的那一半全終止于B, 另一半終止于A. 只要Alice一開始就沿匹配邊走, 后面策略同a. 其它情形不可能在最大匹配中出現, 故不討論. 這正是充分利用了最大匹配的性質.因此對本題先求最大匹配, 然后判斷是否為(1)或(2b), 即可知勝負.代碼如下:
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 //判斷合法狀態
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 //位壓縮存狀態
33 int encode(int x1, int y1, int x2, int y2)
34 {
35 if(y1 > y2 || (y1==y2 && x1 > x2)) //小點放前面, 避免重復狀態
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 //添加狀態轉移的邊
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 //這個匹配函數不分XY集, 因此匹配點雙方的mat標記都要修改
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)并轉化為(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 閱讀(374)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc