#创作计划# 二分图博弈入门

KID2695

2025-10-23 15:42:52

发布于：山东

37阅读

0回复

0点赞

二分图博弈

基本局面：
- 两个玩家轮流行动，每次面临一个二分图 $G=(V,E)$ 和它的一个顶点 $u\in V$ 构成的局面 $(G,u)$ 。一名玩家的行动是必须选择一个与 $u$ 相连的点 $v$ ，随后将顶点 $u$ 以及其所有关联边从图中删去，得到新图 $G'$ 并将新局面 $(G',v)$ 给到另一个玩家。如果某位玩家在其回合开始时，无法选择相连的点就输了
结论：
- 游戏先手必胜，当且仅当顶点 $u$ 是图的 $G$ 最大匹配关键点，也就是说，在图 $G$ 的所有最大匹配中，顶点 $u$ 都是匹配点。
证明：
- 我们设 $G$ 的一个匹配为 $M$ 。
- <1>假如现在局面顶点 $u$ 是图的 $G$ 最大匹配关键点，要求先手移动到的点 $v$ 也在 $M$ 中。然后残余图 $G'$ 的最大匹配最大为 $|M|-1$ ，我们称 $G'$ 的这个匹配为 $M'$ ，显然其为残余图的最大匹配，其变化是去掉了一条边，也就是说现在 $v$ 在 $M'$ 不匹配了，此时顶点 $v$ 不是图的 $G$ 最大匹配关键点。
- <2>假如现在局面存在最大匹配 $M$ 使得 $u$ 未被匹配，显然此时 $u$ 相连的点均在最大匹配中被匹配，转移到的点在最大匹配中，在残余图里因为 $v$ 不被匹配匹配上 $u$ 的情况消失了，所以一定有一个 $v$ 是图的 $G'$ 最大匹配关键点
- 根据博弈论的小性质（详见Nim游戏大学习那篇文章的课后作业），可以证明了。
推广：
- 先手在博弈中选择起点
  - 先手必败当且仅当 $G$ 存在完美匹配
  - 证明与上文同理
- 对于一般图也成立

[NOI2011] 兔兔与蛋蛋游戏

超全的板子
正常写就行了，注意代码里的注释

struct tpg{
	int cnt;
	int ys[M];
	bool vis[M],fla[M];
	bool ck(int u){
		FOR(i,1,num) vis[i]=0;
		return g_find(u);
	}
	bool g_find(int u){
		vis[u]=1;
		for(int i=e.frt[u];i;i=e.nxt[i]){
			int v=e.to[i];
			if(!fla[v] and (ys[v]==0 or ( vis[ys[v]]==0 and g_find(ys[v]) ) ) ){
				ys[u]=v;
				ys[v]=u;
				return 1;
			}
		}
		return 0;
	}
	void unchosepair(int u){
		if(!ys[u]) return ;
		int v=ys[u];
		ys[u]=ys[v]=0;
		--cnt;
		fla[u]=1;
		if(ck(v)) ++cnt;
	}
	void chosepair(int u){
		fla[u]=0;
		if(ck(u)) ++cnt;
	}
	void update(int u,int v){
		if(ys[u]==v){
			fla[u]=fla[v]=1;
			return ;
		}
		int uu,vv;
		uu=vv=0;
		if(ys[u]){
			uu=ys[u];
			ys[uu]=ys[u]=0;
			--cnt;
		}
		if(ys[v]){
			vv=ys[v];
			ys[vv]=ys[v]=0;
			--cnt;
		}
		ys[u]=v;ys[v]=u;
		fla[u]=fla[v]=1;
		++cnt;
		//注意顺序！！！ 
		if(vv&&ck(vv)) ++cnt;
		if(uu&&ck(uu)) ++cnt;
	}
}cb;

FOR(i,1,bj) if(cb.ck(i)) ++cb.cnt;
k=iread();
FOR(i,1,k){
    int nx=iread();
    int ny=iread();
    int u=nb[x][y],v=nb[nx][ny];
    cb.unchosepair(u);
    int tmp_1=cb.cnt;
    cb.chosepair(u);
    int tmp_2=cb.cnt;
    cb.update(u,v);
    if(tmp_1!=tmp_2){//现在兔兔赢 
        int fla=0;
        int tmp_3=cb.cnt;
        for(int j=e.frt[v];j;j=e.nxt[j]){
            int w=e.to[j];
            if(cb.fla[w]) continue;
            cb.unchosepair(w);
            int tmp_4=cb.cnt;
            cb.chosepair(w);
            if(tmp_3==tmp_4){//看每一个点蛋蛋能不能赢 
                fla=1;
                break;
            }
        }
        if(fla) ans[++fz]=i;
    }
    x=iread();
    y=iread();
}
printf("%d\n",fz);
FOR(i,1,fz){
    printf("%d\n",ans[i]);
}
return 0;