P4055 题解
Sharing666
·
·
题解
题意
分析
看到这种向相邻方格移动棋子的题，很容易想到黑白染色建二分图。
相邻的方格只要没有障碍，就连一条双向边。
每次操作可以转换为从左部走到右部或从右部走到左部。
那么，如果这个二分图是完全匹配，无论先手选哪个点，后手都会选最大匹配中这个点对应的点。
因此这时后手有必胜策略。
如果这个图不是完全匹配，一定有一个点剩下来，也就是最大匹配不需要的点。
先手只要一开始把棋子放在这个点，后手无论怎么走，走到的点都在最大匹配内。
于是后手就变成了第一种情况的先手，先手使用上面后手的策略。
因此这时先手有必胜策略。
因为最大匹配方案不止一种，所以所有最大匹配方案剩下的点都可以作为棋子的初始位置。
但是枚举每种方案的时间复杂度太大了。
我们可以先任意求一种方案，设剩下的点为 i。
从 i 开始遍历二分图，假设 i 有一条边一个异侧点 j，j 有一条在已求方案内的边连 i 的同侧点 k，那么一定可以不选 j 到 k 这条边，改选 i 到 j 的边。
按照到现在为止的思路写就可以 AC 这道题。
但是当我看到讨论区的[这个帖子](https://www.luogu.com.cn/discuss/405533)后，发现我没有考虑**图不连通**的情况。~~然而造数据的人貌似也没有考虑。~~
其实很好解决，每个连通块都建一遍图就行。为了方便，我用了 $\text{dfs}$ 建图。
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m,tot; //tot是联通块的编号
int npy[10002]; //匹配方案
char a[102][102];
int mark[102][102]; //每个点所属的联通块
int cnt,head[10002]; //链式前向星
int arrx[4]={0,1,0,-1};
int arry[4]={1,0,-1,0}; //方向数组
bool vis[10002],ans[10002],lft[10002]; //lft记录每个点是否属于左部
struct edge{
int to,nxt;
}e[40002];
void addedge(int A,int B) {
e[++cnt].to=B;
e[cnt].nxt=head[A];
head[A]=cnt;
}
int num(int x,int y) {
return (x-1)*m+y;
} //坐标->编号
void build(int x,int y) {
for(int i=0;i<4;i++) {
int xx=x+arrx[i],yy=y+arry[i];
if(!xx || !yy || xx>n || yy>m || a[xx][yy]=='#') continue;
addedge(num(x,y),num(xx,yy));
if(mark[xx][yy]) continue;
mark[xx][yy]=tot;
build(xx,yy);
}
} //每个联通块dfs建图
bool dfs(int u) {
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].to;
if(!vis[v]) {
vis[v]=1;
if(!npy[v] || dfs(npy[v])) {
npy[v]=u,npy[u]=v;
return 1;
}
}
}
return 0;
} //匈牙利
void dfs2(int u,int rt) {
if(ans[u]) return ;
ans[u]=1;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].to;
if(npy[v]) dfs2(npy[v],rt);
}
} //找其他最大匹配方案不需要的点
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) cin>>a[i]+1;
bool anss=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!mark[i][j] && a[i][j]=='.') {
cnt=0,tot++;
memset(head,0,sizeof head);
memset(e,0,sizeof e);
memset(npy,0,sizeof npy);
build(i,j);
for(int k=1;k<=n;k++)
for(int l=1;l<=m;l++) {
if(mark[k][l]!=tot || (k+l)%2==0) continue;
lft[num(i,j)]=1;
memset(vis,0,sizeof vis);
dfs(num(k,l));
}
bool flag=0;
for(int k=1;k<=n;k++)
for(int l=1;l<=m;l++)
if(mark[k][l]==tot && !npy[num(k,l)]) flag=1;
//判断是否为完全匹配
anss|=flag;
if(!flag) continue;
for(int k=1;k<=n;k++)
for(int l=1;l<=m;l++)
if(mark[k][l]==tot && !npy[num(k,l)]) dfs2(num(k,l),num(k,l));
}
if(!anss) {
printf("LOSE\n");
return 0;
}
printf("WIN\n");
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ans[num(i,j)]) printf("%d %d\n",i,j);
return 0;
}
```
~~码风不好看 TwT。~~