首页 > 其他分享 >二分图博弈 - 二分图·博弈

二分图博弈 - 二分图·博弈

时间:2023-11-07 21:35:55浏览次数:42  
标签:二分 fir 博弈 int dep low 匹配

二分图·博弈

顾名思义 : 二分图 + 博弈

二分图

首先先知道一些基本方法:

  1. 求出二分图最大匹配所必须的点或边,就是求去掉这个点(边)过后最大匹配还是不是原来的最大匹配。

    复杂度更优的方法是先跑一遍 Dinic 求出最大流的任意解与这种解下每条边的残量。分别从原点、汇点开始 tarjan 残量不为 \(0\) 的边,然后判环,所有与原点或汇点在同一个环里的点一定不是必须匹配点。

    比如这个例子:

    二分图最大匹配点的Tarjan求法

    我们保留所有残量不为 \(0\) 的有向边:

    二分图最大匹配点的Tarjan求法2

    然后分别从 \(S\) 和 \(T\) 跑一遍 Tarjan: (浅色边为环上的边)

    二分图最大匹配点的Tarjan求法2

    因此 \(2,3,4,5\) 号点虽然是最大匹配点,但都不是必须点。

  2. 在二分图最大匹配中,任意最大匹配边的两个端点所连接的其他非匹配点最多只有 \(1\) 个,不然就会有更大的匹配,如图:

二分图性质2
(该图片来自网络)

  1. 二分图最小点覆盖(就是选几个点使任意边至少有一个端点处于点集中)的点集大小 \(=\) 二分图最大匹配

    二分图最小边覆盖(就是选几个点使任意点至少有一个连边处于边集中)的边集大小 \(=\) 非孤立点总数 \(-\) 二分图最大匹配

    二分图最小独立点集(就是选几个点使任意边最多只有一个端点处于点集中)的大小 \(=\) 总点数 \(-\) 最小点覆盖 \(=\) 总点数 \(-\) 最大匹配

    事实上这三个公式对任意无向图都成立。

二分图最小边覆盖
(该图片来自网络)

博弈

知道了二分图怎么求最大匹配必须点集,博弈就简单了。

  1. 网格路径有关的题可以给网格黑白染色,连黑白格建二分图。

  2. 二分图博弈的必胜点就是所有最大匹配均需要的格。证明如下

假设在除去当前点后仍存在一个最大匹配,那我们从当前点必然只能沿非匹配边(如果没有,就说明输了)走向另一端的一个点,而另一端的点必然能够通过一条匹配边(必然存在,否则就不是最大匹配了)走回来。

也就是说,从这边不一定能找到一条边过去,但从那边却一定能找到一条边回来,显然某一刻无法再过去,那么就输了。

以下是一份标准的二分图博弈代码(题目:棋盘游戏)

/*
  bug:1.tot 不能初始化为 1 因为 e=0 代表没有边
	  2.是非最大匹配必须点必胜而不是最大匹配必须点必胜,因为是 B 先移动棋子
 */
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define P 100005
#define Q 200005
#define inf 0x3f3f3f3f
int mp[N][N],n,m,tot=1,fir[P],nxt[Q],to[Q],w[Q];
static const int fac[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
pair<int,int>ans[P];
int anscnt;
void add(int x,int y,int z){
	nxt[++tot]=fir[x];
	fir[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
int pos2id(int x,int y){
	return (y-1)*m+x;
}
int dep[P],S,T;
bool bfs(){
	for(int i=pos2id(1,1);i<=T;++i)dep[i]=inf;
	queue<int>q;
	q.push(S);
	dep[S]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int e=fir[x];e;e=nxt[e]){
			int u=to[e];
			if(dep[u]>dep[x]+1&&w[e]>0){
				dep[u]=dep[x]+1;
				q.push(u);
				if(u==T)return 1;
			}
		}
	}
	return 0;
}//网络流标准的 bfs
int dinic(int x,int flow){
	if(x==T)return flow;
	int totf=0;
	for(int e=fir[x];e;e=nxt[e]){
		int u=to[e];
		if(dep[u]==dep[x]+1&&w[e]>0){
			int newf=dinic(u,min(flow,w[e]));
			if(newf==0)continue;
			totf+=newf;
			w[e]-=newf;
			w[e^1]+=newf;
			if(totf==flow)return flow;
		}
	}
	return totf;
}//网络流标准的 dinic
int bel[P],dfn[P],low[P],dfc,stk[P],stl;//bel 代表 x 点所处的环的根节点编号
bool ins[P]={0},piped[P]={0};//piped[x] 代表 x 是否是最大匹配点,不一定必须
void tarjan(int x){
	dfn[x]=low[x]=++dfc;
	ins[x]=1;stk[++stl]=x;bel[x]=x;
	for(int e=fir[x];e;e=nxt[e]){
		if(w[e]==0)continue;
		int u=to[e];
		if(dfn[u]==0){
			tarjan(u);
			low[x]=min(low[x],low[u]);
		}else 
			if(ins[u])low[x]=min(low[x],dfn[u]);
	}
	if(dfn[x]==low[x]){
		for(int u=stk[stl];u!=x;u=stk[--stl])ins[u]=0,bel[u]=x;
		--stl,ins[x]=0;
	}
	return;
}//标准的 tarjan
char ch;
int main(){
	scanf("%d %d",&n,&m);
	for(int y=1;y<=n;++y){
		ch=getchar();while(ch!='#'&&ch!='.')ch=getchar();
		for(int x=1;x<=m;++x){
			mp[x][y]=(ch=='#');
			ch=getchar();
		}
	}
	int nx,ny;
	for(int y=1;y<=n;++y){
		for(int x=1+(y&1);x<=m;x+=2){
			if(mp[x][y]==1)continue;
			for(int f=0;f<4;++f){
				nx=x+fac[f][0],ny=y+fac[f][1];
				if(mp[nx][ny]==0&&nx>0&&nx<=m&&ny>0&&ny<=n){
					add(pos2id(x,y),pos2id(nx,ny),1);
					add(pos2id(nx,ny),pos2id(x,y),0);
				}
			}
		}
	}
	S=pos2id(m,n)+1;T=S+1;
	for(int y=1;y<=n;++y){
		for(int x=1;x<=m;++x){
			if(mp[x][y]==1)continue;
			if((x+y)&1){
				add(S,pos2id(x,y),1);//S -> 左部点
				add(pos2id(x,y),S,0);
			}else{
				add(pos2id(x,y),T,1);//右部点 -> T
				add(T,pos2id(x,y),0);
			}
		}
	}//加边
	while(bfs())dinic(S,inf);//网络流跑出最大匹配 
	for(int e=fir[S];e;e=nxt[e])if(w[e]==0)piped[to[e]]=1;//左部匹配点
	for(int e=fir[T];e;e=nxt[e])if(w[e]!=0)piped[to[e]]=1;//右部匹配点
	tarjan(S);
	if(dfn[T]==0)tarjan(T);//Tarjan
	for(int y=1;y<=n;++y)
		for(int x=1;x<=m;++x)
			if(mp[x][y]==0&&(piped[pos2id(x,y)]==0||bel[pos2id(x,y)]==T-((x+y)&1)))//不是最大匹配点或者在环上
				ans[++anscnt]={y,x};
	printf("%d\n",anscnt);
	sort(ans+1,ans+anscnt+1);
	for(int i=1;i<=anscnt;++i)printf("%d %d\n",ans[i].first,ans[i].second);
	return 0;
}

标签:二分,fir,博弈,int,dep,low,匹配
From: https://www.cnblogs.com/DZhearMins/p/17816062.html

相关文章

  • 二分查找
    一、二分查找其本质就是找一个区间二、整数二分2.1.查找左边界的模板intfindPrior(intleft,intright,inttarget){ while(left<right){ intmid=(left+right)/2; if(a[mid]>=target)right=mid; elseleft=mid+1; } if(a[left]==target......
  • 【笔记】博弈论
    【笔记】博弈论0基本概念&性质0.1博弈论1SG函数ps.通过SG函数来理解三个基本模型,也是不错的选择。1.2定义\(\text{SG}(x)=\text{mex}\{\text{SG}(y_i)\}\)(其中\(y_i\)为\(x\)的后继状态)1.3SG定理由\(n\)个博弈图组成的游戏,设起点(即每个连通分量内入......
  • L2-二分查找
    左闭右闭区间:(另一种为左闭右开区间)注意middle的取值classSolution{publicintsearch(int[]nums,inttarget){//首先关于(left+rigth)/2取舍问题:int类型数据作除法会舍去小数部分intleft=0;intright=nums.length-1;......
  • 二分查找总结
    不考虑重复元素下循环条件l<=rmid=(left+right)>>1(1)如果a[mid]=targetreturnmid(2)如果a[mid]<target搜索[mid+1,right](3)如果a[mid]>target搜索[left,mid-1]如果循环推出仍然没有找到,就标志着没有该元素。二分查找元素起始位置mid=(left+right)>>1需要找到一个......
  • 用二分法寻找第7位数(数组)
    #include<stdio.h>intmain(){  intk=7;  intarr[]={1,2,3,4,5,6,7,8,9,10};  intsz=sizeof(arr)/sizeof(arr[0]);    //元素个数的计算公式  intleft=0;                //左下标  intright=sz-1;  ......
  • 二分查找
    intmain(){ intarr[]={1,2,3,4,5,6,7,8,9,10}; inta=7;//a可改变 intsz=sizeof(arr)/sizeof(arr[0]); intleft=0; intright=sz-1; while(left<=right) { intmid=(left+right)/2; if(arr[mid]>a) { right=mid-1; ......
  • 最小生成树、二分图(11/2)
    到集合得最短距离是指点到集合中的所有点最短距离,集合就是遍历或正选中的数prim#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intn,m;constintN=510;constintINF=0x3f3f3f3f;intg[N][N];intdist[N];boolst[N];intprim(){......
  • 查询算法——顺序查找(优化),二分查找(递归)
    顺序查找顺序查找又称为线性查找,是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构,从第一个元素开始逐个与需要查找的元素x进行比较,当比较到元素值相同时,返回元素m的下标,如果比较到最后都没有找到,则返回-1;时间复杂度为O(n)点击查看代码publicstaticvoidm......
  • Codeforces Round 907 (Div. 2) B. Deja Vu(二分+后缀和+位运算)
    CodeforcesRound907(Div.2)B.DejaVu思路:预处理31位的\(2^x\)存在\(tmp_i\)对于输入\(a_i\),通过查找最后一个二进制1位置,存在\(x0_i\)由题意可知,对于输入的\(x\),如果有\(a_i\)可整除\(x\),则会使\(a_i\)加上\(2^{x-1}\)所以之后除非是\(x-1\),否则无效,因此把输入\(x\)......
  • 数据结构——二分查找(1)
    ``点击查看代码importjava.util.Scanner;publicclassMain{publicstaticint[]a=newint[10];publicstaticvoidmain(String[]args){Scanners=newScanner(System.in);intn=s.nextInt();intb......