【题解】P4055 [JSOI2009] 游戏

link

题目大意

题目说得比较清楚。

题解

前置知识：二分图最大匹配、基础博弈论。

每个点只能走一次的四联通点阵，可以想到二分图匹配。

将其套路地奇偶分点，相邻两点连边（显然不能为 #）。

先求一个最大匹配。

如果是完美匹配，那么 LOSE. 因为小 AA 将棋子放到任意一点，小 YY 都能走匹配边走到另一部，小 AA 就只能走非匹配边。每一点都有一条匹配边，最后小 YY 会走最后一条匹配边，这时所有点都走完了。小 AA 败。

现在考虑 WIN. 首先，若小 AA 选择非匹配点，那么小 AA 必胜。显然，非匹配点的邻接点都为匹配点，否则就不是最大匹配。当小 AA 放下棋子后，小 YY 走到匹配点上。然后，小 AA 走匹配边。则小 YY 此时只能走非匹配边。以非匹配点为开始的一条路径，路径的结尾只能是匹配点。这个点只有一条边连出，为匹配边。最后，小 AA 会通过这条匹配边走到结尾，小 AA 胜。

所以小 AA 选非匹配点时胜利。

再来观察下图。黑点为匹配点，边权为 $1$ 的是匹配边。

我们还有另一种方案：

那么点 $1$ 和 $5$ 都是必胜点。

由此断言：答案为非最大匹配必须点。

如果一个点 $p$ 是非最大匹配必须点，那么存在一个最大匹配，使点 $p$ 不是匹配点。在这个最大匹配上实行上述方案，小 AA 必胜。

我们发现，只需要对一个点尝试增广，如果增广出一条路径，长度与当前最大匹配的路径长度相等，那这个点就是一个非最大匹配必须点。

由于一个点可能在 $X$ 部，也可能在 $Y$ 部，分类讨论的话要写两个增广函数。可以将两部记录匹配点的数组 $cx$ 和 $cy$ 合并，统一为 $cxy$，$cx{y}_i$ 记录点 $i$ 对应的匹配点编号。这样的话需要建双向边，所以其实是用增大常数的代价换来较小的编程复杂度。

时间复杂度 $O(n^4)$.

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 40005;//不能开太大，否则 memset 时会 TLE
int n, m, cnt = 0, fir[N], nxt[N], to[N], vis[N], cxy[N], p[105][105], tot = 0, xt, cans = 0;
char a[105][105];
int dx[5] = {0, 1, 0, -1};
int dy[5] = {1, 0, -1, 0};
struct node {int x, y;
} ans[N];
void ade(int u, int v) {cnt++, nxt[cnt] = fir[u], fir[u] = cnt, to[cnt] = v;cnt++, nxt[cnt] = fir[v], fir[v] = cnt, to[cnt] = u;
}
void getp() {//重标号for (int i = 1; i <= n; i++)for (int j = ((i & 1) ? 1 : 2); j <= m; j += 2)if (a[i][j] == '.')p[i][j] = ++tot;xt = tot;for (int i = 1; i <= n; i++)for (int j = ((i & 1) ? 2 : 1); j <= m; j += 2)if (a[i][j] == '.')p[i][j] = ++tot;
}
void ADE(int x, int y) {//将 (x,y) 与邻接点连边for (int i = 0; i < 4; i++) {int xx = x + dx[i], yy = y + dy[i];if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == '.') ade(p[x][y], p[xx][yy]);}
}
int dfs(int r) {//找增广路径vis[r] = 1;for (int i = fir[r]; i; i = nxt[i])if (!vis[to[i]]) {vis[to[i]] = 1;if (!cxy[to[i]] || dfs(cxy[to[i]])) {cxy[cxy[r]] = 0, cxy[r] = to[i], cxy[to[i]] = r;return 1;}}return 0;
}
void match() {for (int i = 1; i <= xt; i++)if (!cxy[i])memset(vis, 0, sizeof(vis)), dfs(i);
}
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);getp();for (int i = 1; i <= n; i++)for (int j = ((i & 1) ? 1 : 2); j <= m; j += 2)//只枚举偶点if (a[i][j] == '.')ADE(i, j);match();//先求一种最大匹配方案for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (a[i][j] == '.') {memset(vis, 0, sizeof(vis));if (!cxy[p[i][j]] || dfs(cxy[p[i][j]])) ans[++cans].x = i, ans[cans].y = j;}if (!cans) { printf("LOSE"); return 0; }//没有非匹配点printf("WIN\n");for (int i = 1; i <= cans; i++) printf("%d %d\n", ans[i].x, ans[i].y);return 0;
}

END