二分图博弈（知识总结+例题）

思路来源

gzchenben的ppt

算法学习笔记(74): 二分图博弈 - 知乎

https://www.cnblogs.com/Zeardoe/p/16534557.html

知识点总结

以下部分摘自知乎：算法学习笔记(74): 二分图博弈 - 知乎

二分图博弈模型

给出一张二分图和起始点 H ，

A和B轮流操作，每次只能选与上个被选择的点（第一回合则是点 H ）相邻的点，

且不能选择已选择过的点，无法选点的人输掉。

例如，在国际象棋棋盘上，双方轮流移动一个士兵，

不能走已经走过的格子，问谁先无路可走。

结论

考察二分图的最大匹配，如果最大匹配一定包含 H ，那么先手必胜，否则先手必败。

1. 如果最大匹配一定包含 H，那么先手只需要一直按照匹配选点即可。

后手不可能选到非匹配点：

反证法，设如果后手选到一个非匹配点，

设路径为 H→P1→⋯→Pn−1→Pn ，

那么把现在的匹配 {H−P1,…,Pn−2−Pn−1} 换成{P1−P2,…,Pn−1−Pn}，

匹配数不变但不包含 H ，与最大匹配一定包含 H 矛盾。

2. 如果最大匹配不一定包含 H ，考虑某个不包含 H 的最大匹配 M 。

先手无论选择哪个点，它都一定是匹配点，

否则设这个点为 P ，则发现了新匹配 H−P ，与 M 是最大匹配矛盾。

之后后手一直按照匹配选点即可，先手不可能选到非匹配点，此时局面和1相同

方法论

我们可以对删除和不删除 H 的情形分别做二分图最大匹配，

如果删除两个匹配数一样多，说明 H 是可有可无的，存在不包含 H 的最大匹配。

否则，说明 H 是不可或缺的。

具体实现可以根据数据范围选用匈牙利算法或Dinic。

需要注意的是，如果采用Dinic，不要根据有没有 H 点建两次图。

而是在建图时把涉及 H 点的边存下来，

跑完第一次Dinic后再建这些边，第二次Dinic看有没有增加流量。

实际操作的时候，

若H位于二分图左半侧，只需令超级源点S->H边在第二轮连

若H位于二分图右半侧，令H->超级汇点T的边在第二轮连即可

二分图上包含H的边，还是可以在第一轮匹配的时候先连好

因为只要那一条边不连，H对流量就无贡献，

根据网络流的最优性质，答案会优先占用可以贡献流量的点

题目

~~其实也想不到除了用裸题考以外，还能有什么考查方式，因为知识点比较固定~~

2020 China Collegiate Programming Contest Changchun Onsite H题，二分图博弈裸题

t(t<=10)组样例，m(m<=5)位循环密码锁，

密码锁每一位0-9（9和0循环相邻），

每一次拨动可以使i拨到(i-1)%10或(i+1)%10的位置

初始密码为x，Alice和Bob需要轮流拨动，

n( $0<=n<10^m$ )个禁止密码，只要一拨到禁止密码就输了，保证x不在里面

Alice先手，不能操作者输，问双方均最优解下谁必胜

题解

考虑密码各数位和的奇偶性，显然是一个二分图

1. 先不加x的边，跑一次dinic

2. 再把x加上，在残余网络上再跑一次dinic

x是必须点，当且仅当第二次dinic时，流量为1

由于连边时，控制了x一定位于二分图左半端，

所以，第二轮加上边的时候，只加S->x即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10,maxm=3e6+10,INF=0x3f3f3f3f;
int level[maxn];
int head[maxn],cnt;
int ca,n,m,ss,ee,ten[10],st,sum[maxn];
bool ban[maxn];
struct edge{int v,nex;ll w;}e[maxm];
void init(){cnt=0;memset(head,-1,sizeof head);memset(ban,0,sizeof ban);
}
void add(int u,int v,ll w){e[cnt].v=v;e[cnt].w=w;e[cnt].nex=head[u];head[u]=cnt++;
}
//是否为有向图
void add2(int u,int v,ll w,bool op){add(u,v,w);add(v,u,op?0:w);
}
bool bfs(int s,int t){queue<int>q;memset(level,0,sizeof level);level[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();if(x==t)return 1;for(int u=head[x];~u;u=e[u].nex){int v=e[u].v;ll w=e[u].w;if(!level[v]&&w){level[v]=level[x]+1;q.push(v);}}}return 0;
}
ll dfs(int u,ll maxf,int t){if(u==t)return maxf;ll ret=0;for(int i=head[u];~i;i=e[i].nex){int v=e[i].v;ll w=e[i].w;if(level[u]+1==level[v]&&w){ll MIN=min(maxf-ret,w);w=dfs(v,MIN,t);e[i].w-=w;e[i^1].w+=w;ret+=w;if(ret==maxf)break;}}if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 return ret;
}
ll Dinic(int s,int t){ll ans=0;while(bfs(s,t))ans+=dfs(s,INF,t);return ans;
}
int in(){int v;scanf("%d",&v);return v;
}
void link(int i){if(ban[i])return;if(sum[i]==sum[st]){add2(ss,i,1,1);for(int j=0;j<m;++j){int x=(i/ten[j])%10,y=i-x*ten[j];for(int k:{-1,1}){int nx=(x+k+10)%10,ny=y+nx*ten[j];if(ban[ny])continue;add2(i,ny,1,1);}}}else{add2(i,ee,1,1);}
}
int main(){ten[0]=1;for(int i=1;i<=6;++i)ten[i]=ten[i-1]*10;for(int i=1;i<=ten[5];++i)sum[i]=(sum[i/10]+(i%10))%2;scanf("%d",&ca);while(ca--){init();scanf("%d%d",&m,&n);ss=ten[m];ee=ten[m]+1;st=in();for(int i=1;i<=n;++i){ban[in()]=1;}for(int i=0;i<ten[m];++i){if(i==st)continue;link(i);}Dinic(ss,ee);link(st);puts(Dinic(ss,ee)?"Alice":"Bob");}return 0;
}