二分图全解

二分图全解

算法思想

二分图的定义:如果一个图的所有顶点可以分为 X X X和 Y Y Y两个集合,且对于所有边来说,边的两点都不属于同一集合,那么这个图就是二分图

更准确的定义如下:
G = ( V , E ) G=(V,E) G=(V,E)为无向图, V V V为点集, E E E为边集,如果 V V V可被分割成两个互不相交的子集 ( V 1 , V 2 ) (V_1,V_2) (V1​,V2​),且图中每条边 ( i , j ) (i,j) (i,j)两端点分别属于这两个子集,则称 G G G为一个二分图

二分图的相关概念如下:

  1. 匹配:一个只有边的集合,集合中任意两条边无公共点,在一个图的所有匹配中,边数最多的匹配叫做该图的最大匹配
  2. 独立集:两两互不相连的节点集合
  3. 边覆盖:任意节点都至少是某条边端点的边集合,也就是不存在孤立点
  4. 点覆盖:任意边都至少有一个点的点集合,即不存在孤立边
  5. 最小路径覆盖:在一个DAG中,如果存在一个简单路集合(顶点不相交),图的每个顶点都在路上,则该路为一个路径覆盖,最小路径覆盖为所含路径条数最少的路径覆盖

二分图染色

对于给定的一个图,首先需要判断它是否为二分图才能进行相关操作,对于一个无向图来说,当且仅当不存在有奇数条边构成的环时,它才是二分图,这是充要条件,举个例子简单证明

如图,当为奇数环时,根据二分图的定义,可以看到?处无法被赋值

二分图全解
根据二分图的性质可以知道,所有的点被分成了两个集合,那么相连的两个点必然不属于同一集合,因此,可以从任意一点开始,将其设置为1,其邻接点必然为0,以此类推,如果最后出现无法赋值的点,那么必然不是二分图,可以用DFS实现

代码

bool DFS(int u,int c)
{
		col[u]=c;
		for(int i=head[u];~i;i=e[i].next)
		{
				int v=e[i].to;
				if(col[v]==col[u])return 0;
				if(col[v]==-1&&!DFS(v,!col[u]))return 0;
		}
		return 1;
}

当然,如果给的图不是连通图,那么就需要对每个未遍历点进行判断

for(int i=1;i<=n;i++)
	if(col[i]==-1)if(!DFS(i,1))return 0;

二分图相关定理

  1. König: 最小点覆盖=二分图最大匹配
  2. 二分图最小边覆盖: 顶点数-二分图最大匹配
  3. 最小路径覆盖: 顶点数-二分图最大匹配数
  4. 最大独立集: 总点数-二分图最大匹配数

求出最小路径覆盖集合只需要沿着增广路输出即可,输出所有的匹配路

代码

void print(int u)
{
	u+=n;//初始化
	do
		printf("%d ",u=u-n);
	while(vis[u]=1,u=match[u]);
}
for(int i=1;i<=n;i++)
	if(!vis[i])print(i);

最小可相交路径覆盖:Floyd求原图传递闭包

最大匹配算法

首先说明最大匹配的概念,最大匹配指的是在二分图中包含边数最多的一组匹配,是二分图的一类问题,如图,给出了可匹配的关系,求最大匹配可以将原图转换为最大流问题,添加源点和汇点,边权设为1,然后直接跑最大流即可,时间复杂度为 O ( V 2 E ) O(V^2E) O(V2E),但是,给出的图是二分图,可以利用二分图的性质求解,下面为用二分图性质求解的匈牙利算法和KM算法
二分图全解
二分图全解

匈牙利算法

首先给出交替路和增广路概念
交替路:从一个未匹配点出发,依次经过非匹配边,匹配边,非匹配边,…形成的路径为交替路
增广路:从一个未匹配点出发,走交替路,如果途径另一个与起点不同的未匹配点,则这条交替路则称为增广路
注意二分图与求解最大流中的增广路定义不同
给出一个例子进行简单的算法思路说明,这是一个简单的图例,给出了可匹配关系,从节点1开始寻找可匹配点,1可以找到4,之后2再找可匹配点5
二分图全解
但是对于节点3,它的唯一可匹配点只有4,4此时已经和1匹配,那么尝试将1与其他的节点匹配

二分图全解
1可以与5匹配,但是5已经与2匹配,那么尝试将2与其他的节点匹配
二分图全解
2可以与6匹配,所以最后就可以得到最大匹配的结果
二分图全解
这就是匈牙利算法基本思路,根据概念来看,增广路的存在代表可以通过修改当前匹配来增加新的匹配,增广路的本质就是一条路径的起点和终点都是未配对的点,在上述过程中,匹配关系有时需要更改,从已匹配变成未匹配,这个操作被称为“反色”,易证“反色”后的匹配仍然合法且大于等于原匹配

算法步骤:

  1. 初始化节点,从左集合中首个点$$开u始检查
  2. 检查 u u u的邻接点 v v v,若 v v v未匹配,直接匹配两点,否则从 v v v的邻接点出发找增广路,存在增广路就更新匹配关系,即反色,然后匹配 u , v u,v u,v
  3. 找不到最大匹配,即可得到一个最大匹配

代码

bool maxmatch(int u) {//传入左集合节点
    for(int i=head[u]; ~i; i=e[i].next) {//BFS
        int v=e[i].to;
        if(!vis[v]) {//如果没访问过
            vis[v]=1;
            if(!match[v]||maxmatch(match[v]))//如果可以匹配
            {
                match[v]=u;//设定匹配
                return 1;
            }
        }
    }
    return 0;
}

KM算法

KM算法的目的是求出二分图的最大权完美匹配,也就是二分图的两个点集大小需要相同,一般来说,二分图不可能保证两边一定大小相同,所以需要将个数少的一边补点,再将不存在的边权设为0

接下来是与KM相匹配的概念与定理

可行顶标: 给每个节点有个点权 f ( i ) f(i) f(i),对于所有的边 u − v u-v u−v,满足所有的边权 w ( u , v ) ≤ f ( u ) + f ( v ) w(u,v)\le f(u)+f(v) w(u,v)≤f(u)+f(v)

相等子图: 在一组可行顶标下原图的生成子图,包含所有点但只满足 w ( u , v ) = f ( u ) + f ( v ) w(u,v)= f(u)+f(v) w(u,v)=f(u)+f(v)的边 u − v u-v u−v

如果相等子图有完美匹配,则其必然为原图的最大权完美匹配

根据定理,求解最大权完美匹配过程中,需要不断调整可行顶标,使得相等子图拥有完美匹配

一开始不可能直接确定好所有的顶标,所以需要反复确认,修改顶标,当一条边满足 w ( u , v ) = f ( u ) + f ( v ) w(u,v)= f(u)+f(v) w(u,v)=f(u)+f(v),代表其为相等子图的一条边,将其加入图中

设二分图左点集合顶标为 l ( i ) l(i) l(i),右集合顶标为 r ( i ) r(i) r(i),初始化时,因为可行顶标需要满足点权和大于等于边权,不妨设 l ( i ) l(i) l(i)全部为0, r ( i ) r(i) r(i)为对应点所连的边权最大值

调整顶标过程中,目的是构造一个相等子图,也就是不断的向原先构造的子图中添加新边,使得 l ( i ) + r ( j ) = w ( i , j ) l(i)+r(j)=w(i,j) l(i)+r(j)=w(i,j),那么在初始化之后,需要找到一条边 u − v u-v u−v使得 u u u不在二分图最大匹配中,而 v v v在二分图最大匹配中(u点权为0,v点权为最大边权,为了获得最大匹配,默认以v为基准匹配)

对于这样的一条边,我们希望将其加入正在构造的相等子图,就要使得边满足条件,那么顶标和需要减少 △ x = l ( u ) + r ( v ) − w ( u , v ) △x=l(u)+r(v)-w(u,v) △x=l(u)+r(v)−w(u,v)

因为默认 v v v在最大匹配中,改变其点权会影响其他的边(比如边权最大的那条边,如果 v v v点权变了,那么边权最大的那条边的两端点可能就不满足可行顶标的定义了),所以只对 u u u进行操作,也就是 l ( u ) + △ x l(u)+△x l(u)+△x或者 r ( u ) − △ x r(u)-△x r(u)−△x( u u u不一定就在左边),为了放置修改完导致部分顶标不符合定义,所以每次找的 △ x △x △x尽量小

代码(假 O ( n 3 ) O(n^3) O(n3))

bool maxmatch(int u) {
    visr[u]=1;//
    for(int i=1; i<=n; i++) {
        if(visl[i])continue;
        int d=l[i]+r[u]-gragh[u][i];//获得缺的值
        if(d==0) {//代表这条边已经满足了相等子图的条件
            visl[u]=1;//代表可能可以产生匹配
            if(!match[i]||maxmatch(match[i])) {
                match[i]=u;
                return 1;
            }
        } else delta[i]=min(delta[i],d);//更新最小差值
    }
    return 0;
}
int KM() {
    memset(match,0,sizeof(match));//清空匹配
    memset(l,0,sizeof(l));//清空左部点集
    for(int i=1; i<=n; i++) {//初始化右部顶标,默认为边权最大
        r[i]=gragh[i][1];
        for(int j=2; j<=n; j++)
            r[i]=max(r[i],gragh[i][j]);
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)delta[j]=inf;
        while(1) {
            memset(visl,0,sizeof(visl));//清空访问
            memset(visr,0,sizeof(visr));//同上
            if(maxmatch(i))break;
            //继续进行代表i未收录,未匹配成功,需要调整顶标
            int d=inf;
            for(int j=1; j<=n; j++)
                if(!visl[j])d=min(d,delta[j]);
            //visl[j]为1代表已经在构造的增广路上,已经满足d为0了
            //已经无法再提供可以增加相等子图的差值,重复取会死循环
            for(int j=1; j<=n; j++) {
                //这里能修改,是因为匹配失败了
                //也就是经过的点的顶标并不能满足i在最大匹配内,需要尝试修改
                if(visr[j])r[j]-=d;
                if(visl[j])l[j]+=d;
                else delta[j]-=d;//因为r[j]增加了,差值变小了
            }
        }
    }
    for(int i=1; i<=n; i++)res+=gragh[match[i]][i];//累和匹配边
    return res;
}

二分图匹配的复杂度最差为 O ( n 2 ) O(n^2) O(n2)(maxmatch函数),而while(1)循环的最多可以到 O ( n ) O(n) O(n)(尝试与所有节点进行构造匹配),因此整个算法的复杂度最高可达到 O ( n 4 ) O(n^4) O(n4)

可以发现,在修改边的时候,因为每次DFS的起点相同,所以可能每次只修改了一条边,因此有重复搜索的情况,那么将DFS改成BFS,就可以减少搜索的重复性,减少复杂度

代码( O ( n 3 ) O(n^3) O(n3))

int pre[maxn],match[maxn],delta[maxn],graph[maxn][maxn],n,m,res,l[maxn],r[maxn];
int a[maxn],p[maxn],b[maxn],c[maxn];
bool visl[maxn],visr[maxn];
void maxmatch(int u) {
    int x,y=0,d,id=0;
    memset(pre,0,sizeof(pre));//pre用来记录上一条边
    for(int i=1; i<=n; i++)delta[i]=inf;//初始化右点集
    match[y]=u;//初始化匹配关系
    while(1) {
        x=match[y];
        d=inf;//初始化
        visr[y]=1;//访问
        for(int i=1; i<=n; i++) {
            if(visr[i])continue;
            if(delta[i]>l[x]+r[i]-graph[x][i]) {//能否加一条边x-i
                delta[i]=l[x]+r[i]-graph[x][i];
                pre[i]=y;//连接一条未匹配边
            }
            if(delta[i]<d) {//找到一条修改值最少的点
                d=delta[i];//记录数值
                id=i;//记录编号
            }
        }
        for(int i=0; i<=n; i++)
            if(visr[i])l[match[i]]-=d,r[i]+=d;//尝试修改
            else delta[i]-=d;//该边不是最短边,减去后可能成为最短边
        y=id;
        if(match[y]==-1)break;//无法继续匹配
    }
    while(y) {//构造匹配
        match[y]=match[pre[y]];
        y=pre[y];
    }
}
int KM() {
    memset(match,-1,sizeof(match));//清空匹配
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i=1; i<=n; i++) {
        memset(visr,0,sizeof(visr));
        maxmatch(i);//BFS左点集
    }
    for(int i=1; i<=n; i++)
        if(match[i]!=-1)res+=graph[match[i]][i];
    return res;
}

二分图博弈

二分图博弈为一类博弈模型,与二分图的最大匹配有关,其基本模型如下:给出一张二分图和起点,博弈双方轮流操作,每次只能选择与上次被选择点相邻的点,且不能选择已经访问过的点,无法继续操作者判负

设起点为S,有一个结论:如果二分图的任意一个最大匹配一定有S,即S为最大匹配必须点,那么先手必胜,否则先手必败

下面来证明这个结论
如图,给出了一个最大匹配,假设起点S=1,那么按照策略,先手选择2,此时,后手要么无点可选,要么选3(如果2-3存在的话,之后会证明这一点),又到了先手从3开始选择,可以看到,只要先手一直按照寻找匹配点的策略选下去,到最后总会有后手无点可选

如果起点不属于最大匹配中,先手必输,因为先手从起点的下一步必是图中的匹配点之一(之后证明),那么情况和上一段完全相同,只不过是后手按照匹配点的策略来选,到最后总会使先手无点可选
二分图全解
现在进行更详细的证明,如果最大匹配一定包括S,按照先前所说,后手不可能选到最大匹配之外的点,如图,如果后手可以选到非匹配点,例如图中的9,那么图中的最大匹配方案就不止一个:1-2,3-4,5-6,7-8和1-2,4-9,5-6,7-8都可以作为最大匹配,违背了最大匹配一定包括S
二分图全解
如果最大匹配不一定包括S,在这种情况下,可能是有唯一最大匹配,但是S并不在最大匹配中,或者S并不是所有最大匹配的必须点,如图,从9开始,先手的下一步必然是匹配点,否则的话

二分图全解
就会出现下图所属的情况,存在一条边9-10不属于最大匹配,显然,这是不合理的,因为9和10都不属于匹配点,但是它们能够构成匹配,原先的最大匹配就不是最大的了,因此矛盾
二分图全解
接下来的问题就是如何确定起点是否属于最大匹配,方法很简单,直接对有起点和没有起点的原图做最大匹配,如果匹配数相同,代表起点不一定在最大匹配上,否则一定在最大匹配上,可以采用Dinic和匈牙利求解
跑Dinic时不用根据是否有起点建两次图,而是建图的时候保存涉及起点的边,跑完一次Dinic后再建边,查看Dinic是否增加流量

总结一下,对于二分图博弈,分两种大的情况来考虑(实际上是一种情况,但是这样分开更清晰)

  1. 有起点
    有起点的情况下,需要判断起点是否一定属于最大匹配,即为最大匹配必须点,如果是,那么先手必胜,否则先手必输
  2. 无起点
    无起点的情况下,先手需要选择起点,如果先手先选择最大匹配点,后手只需要选择对应的最大匹配的匹配点即可,先手必败,如果图为完全匹配,先手一定会选择最大匹配点,如果不是完全匹配,先手选择非最大匹配点或最大匹配非必须点,那么后手总会首先到最大匹配,所以先手可胜

训练

LuoguP1330

题目大意:略

思路:由题设可知,河蟹之间是不能相连的,那么所有的河蟹可以被划分成两个集合,这恰好符合二分图,那么直接判断给出的图是否是二分图即可,如果不是则无解,若是则选取颜色少的节点,由于题目不保证连通,所以要对每个连通块都进行二分图染色

代码

#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=4e5+10;
int n,m,cnt,res,head[maxn/10],col[maxn/10],dress[2];
struct node {
    int next,to;
} e[maxn<<1];
void Add(int from,int to) {
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
bool DFS(int u,int c) {
    col[u]=c;
    dress[c]++;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(col[v]==col[u])return 0;
        if(col[v]==-1&&!DFS(v,!col[u]))return 0;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    memset(head,-1,sizeof(head));
    memset(col,-1,sizeof(col));
    while(m--) {
        int u,v;
        cin >>u>>v;
        Add(u,v);
        Add(v,u);
    }
    for(int i=1; i<=n; i++)
        if(col[i]==-1) {
            if(!DFS(i,1)) {
                res=0;
                break;
            }
            res+=min(dress[0],dress[1]);
            dress[0]=dress[1]=0;
        }
    res==0? cout <<"Impossible": cout <<res;
    return 0;
}

LuoguP1285

题目大意:略

思路:很重要的一点,如果两个队员不是双向的,那么这两个人一定不能在同一组,因此,在建图的时候,每个点与必不能同一组的点建边,这样的话整个图就可以分成两个点集,也就是二分图,经过染色,整个图也就被分成的多个拥有黑白相间的连通块,显然,每个块只能取全黑或全白,这样的话,整个模型就可以抽象成01背包模型,有k个连通块,每个连通块要么全选黑,要么选白,要求最后分组的差最小,这里的 d p [ i ] [ j ] dp[i][j] dp[i][j]可以解释为在第i个连通块上,能否选j个人,其余见代码

代码

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,acc[121][2],pre[121][121],res,col[121],block,out[121];
bool gragh[121][121],dp[121][121],mark[121];
vector<int>path[121][2];
void DFS(int u,int f,int c) {
    acc[block][col[u]=c]++;//记录下第block个连通块颜色c的个数
    path[block][c].push_back(u);//记录下第block个连通块颜色c有哪些
    for(int i=1; i<=n; i++)
        if(!gragh[i][u]&&i!=f&&u!=i) {
            if(col[i]==-1)DFS(i,u,c^1);//如果相邻点未染色,取反色
            else if(col[i]==c) {
                cout <<"No solution";
                exit(0);
            }
        }
}
int main() {
    cin >>n;
    memset(col,-1,sizeof(col));
    for(int i=1; i<=n; i++) {
        int k;
        while(cin >>k&&k)gragh[i][k]=1;
    }
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            if(gragh[i][j]!=gragh[j][i])gragh[i][j]=gragh[j][i]=0;
    //如果彼此之间不能到达,不连边
    for(int i=1; i<=n; i++)
        if(col[i]==-1) {//没染色
            block++;
            DFS(i,0,1);
        }
    dp[0][0]=1;//初始化
    for(int i=1; i<=block; i++)//多个连通块,可以等价于block个物品
        for(int j=0; j<=n/2; j++) {//容量
            int p=j-acc[i][0];//acc[i][0]为前i个连通块可以拿出0的个数,p为达到j需要的个数
            if(p>=0&&dp[i-1][p])dp[i][j]=1,pre[i][j]=0;
            //如果需要多的0,并且前i-1个块有,代表当前装j个也能满足
            //pre记录先前的转移状态,装的是0
            p=j-acc[i][1];//
            if(p>=0&&dp[i-1][p])dp[i][j]=1,pre[i][j]=1;
            //同上
        }
    for(int i=n/2; i>=0; i--)
        if(dp[block][i]) {//存在一个解使得容量差小
            res=i;
            break;
        }
    int t=res;
    for(int i=block; i>0; i--) {//遍历每个块,回溯求解
        for(int j=0; j<path[i][pre[i][t]].size(); j++)
            //遍历块,将颜色为pre[i][t]的节点录入
            mark[out[++out[0]]=path[i][pre[i][t]][j]]=1;
        t-=acc[i][pre[i][t]];//减去已经使用的块数量
    }
    sort(out+1,out+out[0]+1);//根据题意排序输出
    cout <<out[0]<<" ";
    for(int i=1; i<=out[0]; i++)
        cout <<out[i]<<" ";
    cout <<endl<<n-out[0]<<" ";
    for(int i=1; i<=n; i++)
        if(!mark[i])cout <<i<<" ";
    return 0;
}

POJ1274

题目大意:牛棚与牛直接存在对应关系,每只牛对牛棚有自己的喜好,一个牛棚只能分配给一头牛,一头牛只能分给一个牛棚,计算最多能将牛分配给牛棚多少头

思路:二分图问题,根据对应关系构造二分图然后用匈牙利算法算最大匹配即可

代码

#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=4e4+10;
int n,m,cnt,head[500],match[500];
struct node {
    int next,to;
} e[maxn<<1];
void Add(int from,int to) {
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
bool vis[500];
bool maxmatch(int u) {//传入左集合节点
    for(int i=head[u]; ~i; i=e[i].next) {//BFS
        int v=e[i].to;
        if(!vis[v]) {//如果没访问过
            vis[v]=1;
            if(!match[v]||maxmatch(match[v]))//如果可以匹配
            {
                match[v]=u;//设定匹配
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        int res=0;
        memset(head,-1,sizeof(head));
        memset(match,0,sizeof(match));
        cnt=0;
        for(int i=1; i<=n; i++) {
            int s;
            scanf("%d",&s);
            while(s--) {
                int x;
                scanf("%d",&x);
                Add(i,x+n);
                //Add(x+n,i);这里不用建双边,因为确定下来匹配关系后可以根据匹配反推
            }
        }
        for(int i=1; i<=n; i++) {
            memset(vis,0,sizeof(vis));
            if(maxmatch(i))res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

POJ1325

题目大意:给出两条机器A,B,A有n种工作模式(0~ n-1),B有m种(0~ m-1),一开始都在工作模式0下工作,现在给定k个作业,给出每个作业三元组约束 ( i , x , y ) (i,x,y) (i,x,y),表示可以在A上以x处理或者在B上以y处理,完成工作需要重启以修改机器工作模式,需要安排作业的顺序并分配适当机器使重启次数最少,输出最少的次数

思路:一开始在工作模式0工作,因此可以在工作公式0工作的可忽略,求最少的重启次数,等价于求二分图的最小点覆盖数,等价于求最大匹配,跑匈牙利算法即可

代码

#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=4e4+10;
int n,m,cnt,k,head[500],match[500];
struct node {
    int next,to;
} e[maxn<<1];
void Add(int from,int to) {
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
bool vis[500];
bool maxmatch(int u) {//传入左集合节点
    for(int i=head[u]; ~i; i=e[i].next) {//BFS
        int v=e[i].to;
        if(!vis[v]) {//如果没访问过
            vis[v]=1;
            if(!match[v]||maxmatch(match[v])) { //如果可以匹配
                match[v]=u;//设定匹配
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    while(~scanf("%d",&n)&&n) {
        scanf("%d%d",&m,&k);
        int res=0;
        memset(head,-1,sizeof(head));
        memset(match,0,sizeof(match));
        cnt=0;
        while(k--) {
            int i,x,y;
            scanf("%d%d%d",&i,&x,&y);
            if(x==0||y==0)continue;//跳过工作模式0
            Add(x,y+n);
        }
        for(int i=0; i<n; i++) {
            memset(vis,0,sizeof(vis));
            if(maxmatch(i))res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

LuoguP1263

题目大意:略

思路:如果没有墙,把每一行看做左集合,列为右集合,对于空地将所在行与列连边,匈牙利一遍即可,但是墙将行列割裂开来,因此需要将割裂产生的连通块视做单独的个体,也就是修改遍历范围,具体见代码

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
int m,n,cnt,maze[250][250],match[maxn],head[maxn],res,acch,accz;
int col[maxn],parth[250][250],partz[250][250];
bool vis[maxn];
struct node {
    int next,to;
} e[maxn<<1];
void Add(int from,int to) {//链式前向星
    e[++cnt].next=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
bool maxmatch(int u) {//最大匹配
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(!vis[v]) {
            vis[v]=1;
            if(!match[v]||maxmatch(match[v])) {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    memset(head,-1,sizeof(head));
    memset(col,-1,sizeof(col));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >>maze[i][j];
    for(int i=1; i<=n; i++)maze[i][0]=2;//处理边界值
    for(int i=1; i<=m; i++)maze[0][i]=2;//同上
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(maze[i][j]<2) {//如果不是墙
                if(maze[i][j-1]>1)parth[i][j]=++acch;//前一个点是墙,产生新的连通块
                else parth[i][j]=parth[i][j-1];//不是墙,合并连通块
            }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(maze[i][j]<2) {
                if(maze[i-1][j]>1)partz[i][j]=++accz;//前一个点是墙,产生新的连通块
                else partz[i][j]=partz[i-1][j];//不是墙,合并连通块
            }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(maze[i][j]==0)Add(parth[i][j],partz[i][j]);//如果是空地,左右建边
    for(int i=1; i<=acch; i++) {//遍历每个列连通块
        for(int j=1; j<=accz; j++)vis[j]=0;
        res+=maxmatch(i);//统计匹配量
    }
    cout <<res<<endl;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)//match数组记录了所有匹配边
            if(maze[i][j]==0&&parth[i][j]==match[partz[i][j]])cout <<i<<" "<<j<<endl;
            //空地,且行对应列?
    return 0;
}

2019icpc南京J

题目大意:略

思路:KM模板题,但是需要用到真正的 O ( n 3 ) O(n^3) O(n3)模板

代码

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=512;
int pre[maxn],match[maxn],delta[maxn],graph[maxn][maxn],n,res,l[maxn],r[maxn];
int a[maxn],p[maxn],b[maxn],c[maxn];
bool visl[maxn],visr[maxn];
void maxmatch(int u) {
    int x,y=0,d,id=0;
    memset(pre,0,sizeof(pre));//pre用来记录上一条边
    for(int i=1; i<=n; i++)delta[i]=inf;//初始化右点集
    match[y]=u;//初始化匹配关系
    while(1) {
        x=match[y];
        d=inf;//初始化
        visr[y]=1;//访问
        for(int i=1; i<=n; i++) {
            if(visr[i])continue;
            if(delta[i]>l[x]+r[i]-graph[x][i]) {//能否加一条边x-i
                delta[i]=l[x]+r[i]-graph[x][i];
                pre[i]=y;//连接一条未匹配边
            }
            if(delta[i]<d) {//找到一条修改值最少的点
                d=delta[i];//记录数值
                id=i;//记录编号
            }
        }
        for(int i=0; i<=n; i++)
            if(visr[i])l[match[i]]-=d,r[i]+=d;//尝试修改
            else delta[i]-=d;//该边不是最短边,减去后可能成为最短边
        y=id;
        if(match[y]==-1)break;//无法继续匹配
    }
    while(y) {//构造匹配
        match[y]=match[pre[y]];
        y=pre[y];
    }
}
int KM() {
    memset(match,-1,sizeof(match));//清空匹配
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i=1; i<=n; i++) {
        memset(visr,0,sizeof(visr));
        maxmatch(i);//BFS左点集
    }
    for(int i=1; i<=n; i++)
        if(match[i]!=-1)res+=graph[match[i]][i];
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    for(int i=1; i<=n; i++)cin >>a[i];
    for(int i=1; i<=n; i++)cin >>p[i];
    for(int i=1; i<=n; i++)cin >>b[i];
    for(int i=1; i<=n; i++)cin >>c[i];
    //录入数据
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                if(b[i]+c[j]>a[k])graph[i][j]+=p[k];//如果可以打败,建边
    cout <<KM();
    return 0;
}
/*
4
1 2 3 4
1 1 1 1
0 0 1 1
0 1 1 2
*/

LuoguP6577

题目大意:略

思路:KM模板题

代码

#include <bits/stdc++.h>
#define int long long
#define inf 1e18//这里无穷大0x3f3f3f3f小了
using namespace std;
const int maxn=512;
int pre[maxn],match[maxn],delta[maxn],graph[maxn][maxn],n,m,res,l[maxn],r[maxn];
int a[maxn],p[maxn],b[maxn],c[maxn];
bool visl[maxn],visr[maxn];
void maxmatch(int u) {
    int x,y=0,d,id=0;
    memset(pre,0,sizeof(pre));//pre用来记录上一条边
    for(int i=1; i<=n; i++)delta[i]=inf;//初始化右点集
    match[y]=u;//初始化匹配关系
    while(1) {
        x=match[y];
        d=inf;//初始化
        visr[y]=1;//访问
        for(int i=1; i<=n; i++) {
            if(visr[i])continue;
            if(delta[i]>l[x]+r[i]-graph[x][i]) {//能否加一条边x-i
                delta[i]=l[x]+r[i]-graph[x][i];
                pre[i]=y;//连接一条未匹配边
            }
            if(delta[i]<d) {//找到一条修改值最少的点
                d=delta[i];//记录数值
                id=i;//记录编号
            }
        }
        for(int i=0; i<=n; i++)
            if(visr[i])l[match[i]]-=d,r[i]+=d;//尝试修改
            else delta[i]-=d;//该边不是最短边,减去后可能成为最短边
        y=id;
        if(match[y]==-1)break;//无法继续匹配
    }
    while(y) {//构造匹配
        match[y]=match[pre[y]];
        y=pre[y];
    }
}
int KM() {
    memset(match,-1,sizeof(match));//清空匹配
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i=1; i<=n; i++) {
        memset(visr,0,sizeof(visr));
        maxmatch(i);//BFS左点集
    }
    for(int i=1; i<=n; i++)
        if(match[i]!=-1)res+=graph[match[i]][i];
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    for(int i=1; i<=n; i++)//注意初始化
        for(int j=1; j<=n; j++)
            graph[i][j]=-inf;
    while(m--) {
        int x,y,w;
        cin >>x>>y>>w;
        graph[x][y]=w;
    }
    cout <<KM()<<endl;
    for(int i=1; i<=n; i++)
        cout <<match[i]<<" ";
    return 0;
}

LuoguP4014

题目大意:略

思路:最大总收益直接用KM求解,最小收益需要对边权取反然后跑KM,跑完之后对结果取反即可

代码

#include <bits/stdc++.h>
#define int long long
#define inf 1e18
using namespace std;
const int maxn=512;
int pre[maxn],match[maxn],delta[maxn],graph[maxn][maxn],n,m,res,l[maxn],r[maxn];
bool visl[maxn],visr[maxn];
void maxmatch(int u) {
    int x,y=0,d,id=0;
    memset(pre,0,sizeof(pre));//pre用来记录上一条边
    for(int i=1; i<=n; i++)delta[i]=inf;//初始化右点集
    match[y]=u;//初始化匹配关系
    while(1) {
        x=match[y];
        d=inf;//初始化
        visr[y]=1;//访问
        for(int i=1; i<=n; i++) {
            if(visr[i])continue;
            if(delta[i]>l[x]+r[i]-graph[x][i]) {//能否加一条边x-i
                delta[i]=l[x]+r[i]-graph[x][i];
                pre[i]=y;//连接一条未匹配边
            }
            if(delta[i]<d) {//找到一条修改值最少的点
                d=delta[i];//记录数值
                id=i;//记录编号
            }
        }
        for(int i=0; i<=n; i++)
            if(visr[i])l[match[i]]-=d,r[i]+=d;//尝试修改
            else delta[i]-=d;//该边不是最短边,减去后可能成为最短边
        y=id;
        if(match[y]==-1)break;//无法继续匹配
    }
    while(y) {//构造匹配
        match[y]=match[pre[y]];
        y=pre[y];
    }
}
int KM() {
    memset(match,-1,sizeof(match));//清空匹配
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    for(int i=1; i<=n; i++) {
        memset(visr,0,sizeof(visr));
        maxmatch(i);//BFS左点集
    }
    for(int i=1; i<=n; i++)
        if(match[i]!=-1)res+=graph[match[i]][i];
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin >>graph[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            graph[i][j]*=-1;
    cout <<-KM()<<endl;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            graph[i][j]*=-1;
    res=0;
    cout <<KM()<<endl;
    return 0;
}

LuoguP1971

题目大意:略

思路:利用相对位移的思想,将棋子的移动视为空格的移动,那么先手将空格移动到白子,这与黑子的性质类似,因此将空格看做黑,这样整个迷宫就可以转换成黑白两子间两两匹配的问题,黑白染色,建二分图,根据二分图博弈的思路,分别判断当前移动的点位置在移动前是否为最大匹配必须点,如果是,当前手必赢,否则必输

判断当前点位置是否为最大匹配必须点,可以将点从图中删掉并删掉原先的匹配关系,查看原匹配关系的另一个点是否能组成另一个最大匹配,如果能,代表当前点并不是必须点,则当前手必输(按照最优策略的话),因为当前手下一步必然入最大匹配,记录每一步的当前手是否必输必赢,判断一开始的先手是否错误,需要判断第k轮是否先手必胜而下完后后手必胜,即两个状态都为1,代表这一步先手错了,记录即可

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e3+10;
int n,m,k,sx,sy,cnt,head[maxn],match[maxn];
vector<int>res;
char maze[50][50];
bool color[50][50],vis[maxn/2],block[maxn/2],win[maxn/2];
struct node {
    int next,to;
} e[maxn];
void Add(int from,int to) {//链式前向星
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
int Hash(int i,int j) {//离散化坐标
    return (i-1)*m+j;
}
bool maxmatch(int u) {
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(block[v])continue;//这个点已经被去掉了
        if(!vis[v]) {
            vis[v]=1;
            if(!match[v]||maxmatch(match[v])) {
                match[v]=u;
                match[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            cin >>maze[i][j];
            if(maze[i][j]=='.')//存起点
                sx=i,sy=j;
            else if(maze[i][j]=='O')//标记白点
                color[i][j]=1;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(color[i][j]) {
                if(i+1<=n&&!color[i+1][j]) {//建边
                    Add(Hash(i,j),Hash(i+1,j));
                    Add(Hash(i+1,j),Hash(i,j));
                }
                if(j+1<=m&&!color[i][j+1]) {
                    Add(Hash(i,j+1),Hash(i,j));
                    Add(Hash(i,j),Hash(i,j+1));
                }
                if(i>1&&!color[i-1][j]) {//建边
                    Add(Hash(i,j),Hash(i-1,j));
                    Add(Hash(i-1,j),Hash(i,j));
                }
                if(j>1&&!color[i][j-1]) {//建边
                    Add(Hash(i,j),Hash(i,j-1));
                    Add(Hash(i,j-1),Hash(i,j));
                }
            }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(color[i][j]&&!match[Hash(i,j)]) {//以白点为基础建边
                memset(vis,0,sizeof(vis));
                maxmatch(Hash(i,j));//匹配
            }
    cin >>k;
    for(int i=1; i<=2*k; i++) {
        int id=Hash(sx,sy);
        block[id]=1;//代表这一个已经访问过了,不能作为匹配
        if(match[id]==0)//这一点为非必须/非匹配点,下一步必然在匹配点,下一个人必赢
            win[i]=0;
        else {
            int t=match[id];//t不会与id匹配,因为已经在block上标记了
            match[id]=match[t]=0;
            memset(vis,0,sizeof(vis));
            if(maxmatch(t))win[i]=0;
            else win[i]=1;
            //尝试去掉id开始匹配,如果仍然存在最大匹配,则id为非必须点
            //非必须点为起点,下一个人必在匹配点,下一个人必赢
        }
        cin >>sx>>sy;//录入下一次操作
    }
    for(int i=1; i<=k; i++)
        if(win[2*i-1]&&win[2*i])//如果A本来可以赢,但是下完之后B赢了,代表A下错了
            res.push_back(i);
    int len=res.size();
    cout <<len<<endl;
    for(int i=0; i<len; i++)
        cout <<res[i]<<endl;
    return 0;
}

LuoguP4055

题目大意:略

思路:首先声明一下:

该题数据有问题!该题数据有问题!该题数据有问题!

数据忽略了类似下面两种的数据

3 3  3 3
.##  .##
.##  .##
..#  #..

因此,洛谷上的部分题解可能思路是对的,但是代码从逻辑上是错的,下面给出的代码我自己也不能保证就是对的,因为没有更全面的数据

下面是思路

根据题意,相邻的可行格显然可以连边,那么采用黑白染色的方法将整个可行域分成黑白两部分,这样就可以构造一个二分图了,题目也就转变成了二分图博弈,但是本题的先手是先选点,不是从起点出发
为了先手必胜,那么先手就需要使后手走之后使当前点为最大匹配的起点,这样就和二分图博弈的模型相符合了,那么先手需要找的点就是与最大匹配相连,但可以不属于最大匹配的点,如果整个图是完全匹配,显然是没有这样的点的

最大匹配可能有多个,如果先手走了某个最大匹配的必须点,显然后手就从博弈模型中的“起点”开始走了,先手会输,所以,先手需要走所有最大匹配都非必须的点

为了找所有最大匹配的必须点,可以从一个非必须点开始搜索,假设其颜色为黑,如果经过一个白点搜索还能搜到黑,那么另一个黑点必然也是非必须点,因为这两个点等价,那么它们与公共点组成的边就可以替换原图中最大匹配的一条边,可以画图尝试

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,match[maxn],head[maxn],cnt,ans,res,color[maxn];
int point[1212][1212];
char maze[1212][1212];
bool vis[maxn],une[maxn];
struct node {
    int next,to;
} e[maxn];
void Add(int from,int to) {
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
bool maxmatch(int u) {
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(!vis[v]) {
            vis[v]=1;
            if(match[v]==-1||maxmatch(match[v])) {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
void DFS(int u) {
    if(une[u])return ;
    une[u]=1;
    for(int i=head[u]; ~i; i=e[i].next) {
        int v=e[i].to;
        if(match[v]!=-1)
            DFS(match[v]);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>n>>m;
    memset(match,-1,sizeof(match));
    memset(head,-1,sizeof(head));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >>maze[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(maze[i][j]=='.') {
                point[i][j]=++ans;//离散化
                if((i+j)%2==0)color[ans]=1;//染色,一个小技巧
             	//只染色了偶数和格,可以保证奇数和格必为0
            }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(maze[i][j]=='.') {//建图
                if(point[i+1][j]) {//利用已经离散化的坐标来代替
                    Add(point[i][j],point[i+1][j]);
                    Add(point[i+1][j],point[i][j]);
                }
                if(point[i][j+1]) {
                    Add(point[i][j],point[i][j+1]);
                    Add(point[i][j+1],point[i][j]);
                }
            }
    for(int i=1; i<=ans; i++)//构造最大匹配
        if(color[i]) {//以黑点为基准
            memset(vis,0,sizeof(vis));
            if(match[i]==-1)
                res+=maxmatch(i);
        }
    if(cnt/2==res||(ans/2==res&&cnt/2+1==ans)) {//特判是否无解
        cout <<"LOSE"<<endl;
        return 0;
    }
    cout <<"WIN"<<endl;
    for(int i=1; i<=ans; i++)//反标记,代表已经在最大匹配上
        if(match[i]!=-1)match[match[i]]=i;
    for(int i=1; i<=ans; i++)if(match[i]==-1)DFS(i);
    //如果是非必须点,找另一个非必须点
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(une[point[i][j]])//根据离散化坐标判断是否为非必须点
                cout <<i<<" "<<j<<endl;
    return 0;
}
/*
3 3
.##
.##
..#
*/

总结

二分图最基础的知识点就是最大匹配和染色,其余的知识点都是在这两点上延伸拓展的,需要深刻理解,由LuoguP1285可以看到,二分图可以将整个图变成一个个具有双重性质的连通块,而如果将这些连通块套入背包模型,便可以用DP的思路来解决问题,这是非常巧妙的
二分图,准确来说,是一种思想,一种思维,如何将问题转换成二分图,如何套用二分图模型解决问题,这是需要掌握的

KM算法是最大匹配的拓展,确切的来说,它利用了顶标与边权来进行取值约束,通过不断的修改顶标间接的修改所取的边与匹配关系,最后获得最大权匹配

二分图的问题大多数可以用网络流的其他算法来解决,但是由于二分图的特殊性,二分图本身的相关算法还是更加适配自身的问题

参考文献

  1. 《啊哈算法》
  2. 图论 —— 二分图
  3. 《算法训练营:海量图解+竞赛刷题》
  4. 二分图学习笔记
  5. 2019浙师大暑期ACM集训第二讲 图论(二) 二分图和网络流
  6. 「二分图」学习笔记
  7. P1285 队员分组 题解
  8. P1263 [CEOI2002] Royal guards 题解
  9. 同济大学2020ICPC暑假训练 8月16日 二分图及其应用
  10. 算法学习笔记(74): 二分图博弈
  11. 二分图博弈算法讲解及证明 (21夏 学习笔记)
  12. 1971兔兔与蛋蛋题解
上一篇:Java8新的异步编程方式 CompletableFuture


下一篇:多个线程操作一个变量(synchronized)