例题：在N×M的迷宫中有一个棋子，小 AA 首先任意选择棋子放置的位置。然后，小 YY 和小 AA 轮流将棋子移动到相邻的格子里。游戏的规则规定，在一次游戏中，同一个格子不能进入两次，且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。
输入格式：输入数据首先输入两个整数 N,M，表示了迷宫的边长。接下来 N行，每行 M个字符，描述了迷宫。
输出格式：若小 AA 能够赢得游戏，则输出一行 WIN，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出，每行一个。否则输出一行 LOSE
分析：发现每次移动一定是从一个黑点到达一个白点，或者反过来。所以可以对于棋盘进行染色然后连边。
考虑一下必胜策略。如果选择从一个匹配点开始走，另外一个人沿着匹配点走，那么就输了，因为匹配点不一定有出边了。如果选择从一个非匹配点开始走，另外一个人无论怎么走都只能走到一个匹配点（或者无路可走），因为如果另外一个人可以走到一个非匹配点，意味着这两个点可以匹配，所以不存在这种情况。那么，先手只需要沿着匹配边走就一定能够做到必胜。所以黑白染色之后连边，找到所有不一定在最大匹配中的点就好了。跑网络流就会快很多。但是怎么判断一个点是否在不一定在最大匹配中呢？把所有和S相连的(还有剩余流量的边连接的)点全部扣下来，这些点一定满足条件。为什么呢？首先不在当前的这个匹配中的点一定会被计算。如果一个点在匹配中，但是他被连上了，那么一定是通过一个没有被匹配上的点，到达当前点的匹配点，在连回来的，这样子意味着可以交换匹配。和T相连的点同理解决即可。
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int M = 105; const int N = 1e4 + 50; typedef long long ll; int S, T, cnt = 1, maxn, tot, dn, dm, ans; int dep[N], head[N], temp[N], id[M][M], kk[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; char s[M][M]; bool vis[N], is[N], color[N]; struct Edge{ int nex, to, val; }e[N << 3]; inline int min(int a, int b) { return a < b ? a : b; } inline void add(int a, int b, int c){ e[++cnt] = {head[a], b, c}, head[a] = cnt; e[++cnt] = {head[b], a, 0}, head[b] = cnt; } bool bfs(){ memset(dep, 0, sizeof(dep)); queue<int> q; q.push(S); dep[S] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = head[u]; i; i = e[i].nex){ int to = e[i].to; if(!dep[to] && e[i].val){ dep[to] = dep[u]+1; q.push(to); } } } return dep[T]; } ll dfs(int u, int flow){ if(u == T) return flow; ll out = 0, k; for(int i = temp[u]; i && flow; i = e[i].nex){ temp[u] = i; if(!e[i].val) continue; int to = e[i].to; if(dep[to] == dep[u]+1 && (k = dfs(to,min(flow,e[i].val)))){ e[i].val -= k; e[i^1].val += k; flow -= k; out += k; } } if(!out) dep[u] = 0; return out; } void Dinic(){ while(bfs()){ for(int i = S; i <= T; ++i) temp[i] = head[i]; maxn += dfs(S, 1e9); } } void DFS(int u, int k){ vis[u] = 1; if(color[u] == k) ++ans, is[u] = 1; for(int i = head[u]; i; i = e[i].nex){ int to = e[i].to; if(e[i].val == k && !vis[to]) DFS(to, k); } } int main(){ scanf("%d%d", &dn, &dm); for(int i = 1; i <= dn; ++i) scanf("%s", s[i] + 1); for(int i = 1; i <= dn; ++i) for(int t = 1; t <= dm; ++t) if(s[i][t] != '#') id[i][t] = ++tot; T = tot + 1; for(int i = 1; i <= dn; ++i) for(int t = 1; t <= dm; ++t) if(s[i][t] == '.'){ if(((i + t) & 1)){ add(S, id[i][t], 1), color[id[i][t]] = 1; for(int j = 0; j < 4; ++j){ int dx = i + kk[j][0], dy = t + kk[j][1]; if(dx >= 1 && dx <= dn && dy >= 1 && dy <= dm) add(id[i][t], id[dx][dy], 1); } } else add(id[i][t], T, 1); } Dinic(); DFS(S, 1); memset(vis, 0, sizeof(vis)); DFS(T, 0); if(ans){ puts("WIN"); for(int i = 1; i <= dn; ++i) for(int t = 1; t <= dm; ++t) if(is[id[i][t]]) printf("%d %d ", i, t); } else puts("LOSE"); return 0; }