Solution
补一篇二分图博弈
这个博客写的很详细qwq：Code
//By Menteur_Hxy#include#include #include #include #include #define F(i,a,b) for(register int i=(a);i<=(b);i++)#define E(i,u) for(register int i=head[u],v;i;i=nxt[i])#define add(a,b) nxt[++cnt]=head[a],to[cnt]=b,head[a]=cntusing namespace std;const int N=50;int mv[5]={0,1,0,-1,0};int n,m,tot,top,tim,X,Y,cnt;bool mp[N][N],jud[2010],ban[N*N];int head[N*N],to[N*N*N*N],nxt[N*N*N*N],vis[N*N];int id[N][N],mat[N*N],ans[1010];char ch[N];bool dfs(int u) { if(ban[u]) return false; E(i,u) if(vis[(v=to[i])]!=tim&&!ban[v]) { vis[v]=tim; if(!mat[v] || dfs(mat[v])) { mat[v]=u;mat[u]=v; return true; } } return false;}int main() { cin>>n>>m; F(i,1,n) { scanf("%s",ch+1); F(j,1,m) if(ch[j]=='O') mp[i][j]=0; else if(ch[j]=='X') mp[i][j]=1; else if(ch[j]=='.') mp[i][j]=1,X=i,Y=j; } F(i,1,n) F(j,1,m) id[i][j]=++tot; F(i,1,n) F(j,1,m) if(mp[i][j]) F(k,0,3) { int x=i+mv[k],y=j+mv[k+1]; if(mp[x][y]||x<1||x>n||y<1||y>m) continue; add(id[i][j],id[x][y]); add(id[x][y],id[i][j]); } F(i,1,n) F(j,1,m) if(mp[i][j]) ++tim,dfs(id[i][j]); int q; cin>>q; F(i,1,q+q) { int now=id[X][Y],v=mat[now]; ban[now]=true;//!!! if(v) { mat[now]=mat[v]=0; ++tim; jud[i]=!dfs(v); } cin>>X>>Y; } F(i,1,q) if(jud[i+i-1]&jud[i+i]) ans[++top]=i; printf("%d\n",top); F(i,1,top) printf("%d\n",ans[i]); return 0;}