二分图学习笔记 Step2——二分图最大匹配

· · 算法·理论

二分图最大匹配

定义

对于一张二分图 G，一个匹配指的是一条边，选取最大的边集 E 且 E 中任意两条边不共点，那么称 E 是 G 的一组最大匹配。

最大匹配不一定唯一。

最大匹配中任意一条边的两个端点一定在不同点集内（似乎是废话，因为二分图）。

最大匹配中有一些点和一些边是必选的，有一些是可选的。

二分图最大匹配的寻找——匈牙利

枚举左部的点 x，从尚未访问的点出发 dfs。若到达右部的点 y，且 y 尚未匹配（即 match_y=0），则 y 与 x 匹配，终止 dfs；若点 y 已经匹配（即 match_y \neq 0），则从左部的 match_u 再次出发 dfs。

重复执行上述操作，直到所有路径搜索完毕证明最大匹配无法增加。

模板题——P3386

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, e;
int vis[100005], match[100005];
vector<int> nbr[100005];
bool xyl(int cur)
{
    for(int nxt:nbr[cur])
    {
        if(!vis[nxt])
        {
            vis[nxt]=1;
            if(!match[nxt]||xyl(match[nxt]))
            {
                match[nxt]=cur;
                return 1;
            }
        }
    }
    return 0;
}
signed main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++)
    {
        int x, y;
        cin>>x>>y;
        nbr[x].emplace_back(y);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        if(xyl(i))ans++;
    }
    cout<<ans;
}

例题——P10937

建模：

  1. 把行和列分别看作二分图的左部和右部结点。
  2. 把车看作一条边，边的端点是车所在的行和列。
  3. 行之间不可能放同一个车，列亦然，因此该图为二分图。
  4. 求放置最多的车且不互相攻击，转换为选最多的边不共点。
  5. 禁止位置所在的行不向所在的列连边即可。

例题——P1129

建模：

  1. 把行和列分别看作二分图的左部和右部结点。
  2. 把黑色格子看作一条边，边的端点是格子所在的行和列。
  3. 跑二分图最大匹配得到 ans，若 ans=n，输出 Yes，否则输出 No。
  4. 当主对角线上全是格子的时候，则最大匹配为 n。
  5. 若最大匹配为 n 时，建模中连的边两两交叉，则可以通过交换得到平行边。

例题——P2055

建模：

  1. 在校生有床，外校生没有床。
  2. 外校生和留校生都需要床，设该人数为 tot。
  3. 将人视为左部的点，床视为右部的点，一个人睡他认识的人的床视为一条边。得到二分图。
  4. 在校生且回家的不需要参与建图。
  5. 留校生需要向自己的床连边，还要向自己认识的人的床连边。
  6. 外校生需要向认识的人的床连边。
  7. 跑最大匹配，若 ans \ge tot，有解。