Vexoben
Jul 13, 2018
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1443
题意
给定一个n*m的棋盘，有些地方有障碍。AA和YY做游戏。AA先在任意位置放一颗棋子，随后YY和AA交替移动棋子，走过的格子不能走，最先不能走的人输。问AA是否有必胜策略。如果有，输出所有可能的放置棋子位置。
n,m<=100
题解
首先，给定一个棋盘，如果将它黑白染色，我们可以得到二分图。
这时可以观察到一个性质：如果AA将棋子放在一个不在最大匹配内的格子上，他是必胜的。
因为YY移动时，它要么不能走，要么移动到一个匹配点上，否则就会与“二分图最大匹配中无增广路”相矛盾。这时AA只要走到相应的匹配点，就可以保证必胜了。
同理可知，如果最大匹配包含了所有的点，那么AA必败。
然后考虑如何输出可行点。一个点是可行点，当且仅当存在一个最大匹配不包含这个点。
下面给出最大流的求解方法：
先求出任意一个最大匹配。从S开始，走cap=1的边，走到所有X部的点都是答案；从T开始，走cap=0的边，走到所有Y部的点都是答案。
可以这样理解：不在最大匹配中的点显然会被走到。而一个最大匹配中的点，需要一个不在最大匹配中的点来代替它。从X部走cap=1的边到Y部，相当于是X部的未匹配点找到一个Y部点。如果这时还能通过cap=1的边走回来，那就是找到了原来和Y部点匹配的X部点。这时就可以用这个点代替那个X部的匹配点。
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
const int u[4]={1,-1,0,0};
const int v[4]={0,0,1,-1};
char s[105];
int a[105][105];
int n,m,E=1,V,S,T,c1,c2,flag=0;
int x[N],y[N],belong[N],vis[N],use[N],ans[N];
int fir[N],nex[N<<1],arr[N<<1],cap[N<<1],dis[N],cur[N<<1];
queue<int> Q;
pair<int,int> pnt[N];
map<pair<int,int>,int> Map;
namespace FastIO {
template<typename tp> inline void read(tp &x) {
x=0; register char c=getchar(); register bool f=0;
for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
if(f) x=-x;
}
template<typename tp> inline void write(tp x) {
if (x==0) return (void) (putchar('0'));
if (x<0) putchar('-'),x=-x;
int pr[20]; register int cnt=0;
for (;x;x/=10) pr[++cnt]=x%10;
while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x) {
write(x);
putchar('\n');
}
}
using namespace FastIO;
inline void Add_Edge(int x,int y,int c) {
nex[++E]=fir[x];
fir[x]=E; arr[E]=y; cap[E]=c;
nex[++E]=fir[y];
fir[y]=E; arr[E]=x; cap[E]=0;
}
int bfs() {
memset(dis,0x3f,sizeof(int)*(V+10));
Q.push(S); dis[S]=0;
while (!Q.empty()) {
int x=Q.front(); Q.pop();
for (int i=fir[x];i;i=nex[i]) {
if (!cap[i]) continue;
if (dis[arr[i]]>dis[x]+1) {
dis[arr[i]]=dis[x]+1;
Q.push(arr[i]);
}
}
}
return dis[T]<inf;
}
int dfs(int x,int maxflow) {
if (x==T||!maxflow) return maxflow;
int ans=0;
for (int i=cur[x];i;cur[x]=i=nex[i]) {
int v=arr[i];
if (dis[v]==dis[x]+1&&cap[i]) {
int del=dfs(v,min(maxflow,cap[i]));
cap[i]-=del; cap[i^1]+=del;
ans+=del; maxflow-=del;
}
}
return ans;
}
void Solve(int x,int t) {
vis[x]=1;
if (belong[x]==t) {
ans[x]=1;
if (x!=S&&x!=T) flag=1;
}
for (int i=fir[x];i;i=nex[i]) {
if (cap[i]==t&&!vis[arr[i]]) Solve(arr[i],t);
}
}
int main() {
read(n); read(m);
for (int i=1;i<=n;i++) {
scanf("%s",s+1);
for (int j=1;j<=m;j++) a[i][j]=(s[j]=='.');
}
S=++V; T=++V;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (a[i][j]==0) continue;
++V; pnt[V]=mp(i,j); Map[mp(i,j)]=V;
if ((i+j)&1) x[++c1]=V;
else y[++c2]=V;
}
}
for (int i=1;i<=c1;i++) belong[x[i]]=1;
for (int i=1;i<=c2;i++) belong[y[i]]=0;
for (int i=1;i<=c1;i++) Add_Edge(S,x[i],1);
for (int i=1;i<=c2;i++) Add_Edge(y[i],T,1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((i+j)%2==0) continue;
int r=Map[mp(i,j)];
if (!r) continue;
for (int k=0;k<4;k++) {
int t=Map[mp(i+u[k],j+v[k])];
if (!t) continue;
Add_Edge(r,t,1);
}
}
}
while (bfs()) {
memcpy(cur,fir,sizeof(int)*(V+10));
dfs(S,inf);
}
memset(vis,0,sizeof(vis));
Solve(S,1); Solve(T,0);
if (!flag) return 0*puts("LOSE");
puts("WIN");
for (int i=3;i<=V;i++) {
if (ans[i]) {
write(pnt[i].first); putchar(' '); writeln(pnt[i].second);
}
}
return 0;
}