二分图匹配的巧妙应用相当巧妙!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 阅读(360)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc