学习心得 - 算法 - 匈牙利（增广路算法）

· · 算法·理论

整个二分图，就是一个不断修改的 Romatic 史。

情人节特辑？或许是吧。

什么是二分图最大匹配

左边 n 个点，右边 m 个点，相连 e 条边。

我们要让左右 ♥ 两 ♥ 两 ♥ 匹 ♥ 配 ♥，求最大 ♥ 匹 ♥ 配 ♥ 对 ♥ 数。

算 ♥ 法 ♥ 演 ♥ 示

在这里我们使用匈牙利算法。

首先我们需要一些人。

左边是 ♥ 男 ♥ 孩 ♥ 纸。

右边是 ♥ 女 ♥ 孩 ♥ 纸。

我们把此题的样例 2 画下来就是这样的。

注意到我们可以成全最多 2 对：

还有其他很多匹配方法，但是答案为 2。

我们想如何匹配？

我们考虑枚举左侧节点，再通过搜索搜出他的 npy 匹配节点。

我们通过图片来理解一下。

男 1 号

我们枚举 NPY 时可以枚举到女 1 号和女 2 号。

女 1 号

她还没有 NPY，所以我们将女 1 号的 NPY 设为男 1 号。我们定 f_1=1，设置女 1 号的 NPY，同时设置 npy_1=1，代表这个点找到了 NPY。

女 2 号

男 1 号已经有 NPY 了，所以我们不修改女 2 的状态。

记录答案

男 1 号找到了 NPY，匹配成功记录答案！

男 2 号

孤独的男 2 号无法匹配 NPY，匹配失败 T^T。

男 3 号

男 \sout{1} 号的强力竞争者！

女 1 号

已经被男 1 占有了！

我们先让男 3 抢先占有女 1，npy_1=3。

接着，让男 1 做出抉择：男 1 还可以选女 2！

太好了，我们的匹配情况就变成了：

女 2 号

已经被男 1 号占有了！而且男 3 已有 NPY，不处。

记录答案

男 3 号找到了 NPY，匹配成功记录答案！

男 4 号

啥也不是。。。

女 2 号

男 4 发现女 2 已有 NPY 男 1。

无语。最终没有 NPY T^T

最终状态

匹配对数 2。

匈牙利算法

我们刚刚做的匹配操作，就是匈牙利算法。

家长：建议让 OI 不要再伤害青少年之匈牙利算法。

考虑使用 npy 表示女方的 NPY，然后枚举男方。

  1. 首先枚举占有女 v 号。
  2. 然后判断是否能成功 ♥ 与 ♥ 女 ♥ v ♥ 号 ♥ 配 ♥ 对 ♥。细说配对。
    • 要是 npy_v=0，那好皆大欢喜。
    • 否则是遇上情敌了，以出题人给的强悍力量让原有 npy_v 考虑换 NPY，要是换不了那么占有失败，否则匹配成功。
  3. 统计一下有多少次匹配成功即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int n,m,ee,U,V,npy[N],ncnt;
int found[N];
bool e[N][N];
bool dfs(int p){
    for(int v=1;v<=m;v++)if(e[p][v]&&!npy[v]){
        npy[v]=1;
        if(!found[v]||dfs(found[v])){
            found[v]=p;
            return 1;
        }
    }
    return 0;   
}
int main(){
    cin>>n>>m>>ee;
    for(int i=1;i<=ee;i++){
        cin>>U>>V;
        e[U][V]=1;
    }
    for(int i=1;i<=n;i++){
        memset(npy,0,sizeof(npy));
        if(dfs(i))++ncnt;
    }
    cout<<ncnt;
    return 0;
}

最后，祝愿广大 OIer 早日找到 NPY （虽然这不可能

——From Anguei