二分图最大匹配及其各种各样奇怪的概念与算法

二分图

对于一张图中的点，可以分成两组，其中，同一组内的点 互不相连 ，则我们成这张图为二分图

由此可得一些东西

• 我们可以通过交叉染色判定二分图，如果图$G$是二分图，则只需要 两种 颜色来染色
• 「 不含 奇数边环的图」就是二分图

匹配

匹配是一张图中一部分边的集合，这个集合内的边没有 相交点

完美匹配

如果一个匹配中包含了这张图内所有的点，我们就称这个匹配为 完美匹配

最大匹配问题

给你一张图，询问这张图的匹配最多包含多少个点，这个匹配被成为 最大匹配 ，这个问题被称为 最大匹配问题

匈牙利算法

交替路

从未匹配点出发依次经过匹配边与未匹配边的路我们称作交替路

增广路

从为匹配点出发走交替路走到一个未匹配点的交替路我们称其为增广路

增广路的非匹配边定会比匹配边多一条，故此我们可以通过查找增广路来改进现有匹配，如果一个匹配已走不出增广路那他就是最大匹配了

与最大匹配相关的定理

最小路径覆盖

点数 – 最大匹配数 = 最小路径覆盖

可谓是相当好理解了，如果有一个最小路径覆盖比当前少，则最大匹配一定会比当前多，那这还是最大匹配?

最小点覆盖

最小点覆盖 = 最大匹配数

详见 : [ König定理 ]

代码

// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
using namespace std;

//edge start 
struct edge{
    int to,next;
}e[1100000];
int ehead[2100],ecnt;

inline void add(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}

int u,v;
int n,m,ee;
int ans;

bool vis[2100];
int cx[1100],cy[1100];

int dfs(int now){
    for(int i=ehead[now];i;i=e[i].next){
        if(!vis[e[i].to]){
            vis[e[i].to]=true;
            if(cy[e[i].to]==false||dfs(cy[e[i].to])){
                cx[now]=e[i].to;
                cy[e[i].to]=now;
                return true;
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d%d",&n,&m,&ee);
    for(int i=1;i<=ee;i++){
        scanf("%d%d",&u,&v);
        if(u<=n&&v<=m){
            add(u,v);
        }
    }
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        ans+=dfs(i);
    }       
    printf("%d",ans);
}

最大流方法

最大流也可以求解二分图最大匹配

设二分图中两组互不相连接的点集中任意一个集合为$U$,另一个为$V$，然后

超级源点
超级汇点

别忘了反向边