二分图的匹配及算法

Enoch2013 · 2025-02-27 19:44:51 · 算法·理论

注：本专栏参考自《算法竞赛进阶指南》

什么是二分图

二分图，又叫双分图、二部图、偶图。如果一张无向图的 N 个节点 (N \ge 2) 可以分成 A,B 两个非空集合，其中 A \cap B = \emptyset，并且在同一集合内没有边相连，那么，我们称这张无向图为二分图。A,B 分别称为二分图的左部和右部。

二分图判定

定理：如果一张无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。

证明

根据该定理，我们一般使用黑白染色法进行二分图的判定。思想：我们使用黑白颜色来标记图中的每个点，如果一个节点被标记了，那么，与该节点相邻的节点应被标为与该节点相反的颜色，若产生冲突，那么，这张图就存在奇环（不是二分图）。

根据以上思想，我们写一下代码，我这边采用的是深度优先遍历，时间复杂度为 O(N + M)，代码如下：

// ...
void dfs(int u, int c)
{
    col[u] = c;
    for (int i = pre[u]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!col[to])
            dfs(to, 3 - col);
        else if (col[to] == col[u])
        {
            flag = true;
            return;
        }
    }
}
int main()
{
    // ...
    for (int i = 1; i <= n; i++)
    {
        flag = false;
        if (!col[i])
        {
            dfs(i, 1);
            if (flag)
            {
                printf("No\n");
                return;
            }
        }
    }
    printf("Yes");
    return 0;
}

例题：

P1525 [NOIP 2010 提高组] 关押罪犯

思路：

有些同学可能会问：这不裸的并查集吗？干嘛要用二分图做？这也是我的第一反应。但是如果你仔细分析题目，你会发现，我们可以使用二分答案（大家应该都知道，所以就不说了）二分那个怨气值，我们可以把罪犯当作节点，在怨恨值大于这次二分的中值的罪犯连无向边。我们便得到了一张无向图，而这张无向图又要被分成两个部分（其实就是监狱），并且集合内部没有边（自行理解），非常符合我们的二分图性质，所以我们就去判断是否是二分图，如果是，则令二分上界为当前中值，否则令下界为中值加一。

代码：

如果思路理解了，同学们可以自己写一下代码，或者看一下我的代码。

#include <bits/stdc++.h>
#define int long long
#define N 400005
using namespace std;
int n, m, pre[N], k = 0, col[N];
bool flag;
struct node
{
    int x, y, z;
    bool operator <(const node &other) const { return z < other.z; }
} b[N];
struct Edge
{
    int to, ne;
} a[N];
void add(int u, int v)
{
    a[++k] = (Edge){v, pre[u]};
    pre[u] = k;
}
void dfs(int x, int c)
{
    col[x] = c;
    // sum[c]++;
    for (int i = pre[x]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!col[to])
            dfs(to, c ^ 1);
        else if (col[to] == col[x])
            flag = false;
    }
}
bool check(int pos)
{
    memset(pre, 0, sizeof pre);
    memset(a, 0, sizeof a);
    for (int i = pos + 1; i <= m; i++)
        add(b[i].x, b[i].y), add(b[i].y, b[i].x);
    flag = true;
    memset(col, 0, sizeof col);
    for (int i = 1; i <= n; i++)
        if (!col[i])
        {
            dfs(i, 0);
            if (!flag)
                return false;
        }
    return true;
}
signed main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%lld%lld%lld", &b[i].x, &b[i].y, &b[i].z);
    if (m == 1)
    {
        printf("0");
        return 0;
    }
    sort(b + 1, b + m + 1);
    int l = 0, r = m, mid;
    while (l + 1 < r)
    {
        mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%lld", b[r].z);
    return 0;
}

二分图最大匹配

“任意两条边都没有公共断点”的边的集合被称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

对于任意一组匹配 S（S 是一个边集），属于 S 的边被称为“匹配边”，不属于 S 的边被称为“非匹配边”。匹配边的端点被称为“匹配点”，其它节点被称为“非匹配点”。如果二分图中存在一条连接两个非匹配点的路径 path，使得非匹配边与匹配边在 path 上交替出现，那么称 path 是匹配 S 的增广路，也称交错路。

增广路具有以下性质：

长度 len 为奇数；
路径上 1,3,5,\cdots,len 条边是非匹配边，第 2,4,6,\cdots,len-1 条边是匹配边。

正因为以上性质，如果我们把路径上的所有边的状态取反，原来的匹配边变成非匹配边，原来的非匹配边变成匹配边，那么，得到的新的边集 S' 仍然是一组匹配，并且匹配边数增加了一。进一步可得到推论：二分图的一组匹配 S 是最大匹配，当且仅当图中不存在 S 的增广路。

概念比较多，建议同学们仔细研读（我自己读了不下五遍），理解清楚，并自己画个图，再继续读下面的内容。

匈牙利算法（增广路算法）

匈牙利算法，又称增广路算法，用于计算二分图的最大匹配。它的主要过程是：

设 S = \emptyset，即所有的边都为非匹配边；
寻找增广路 path，把路径上所有边的匹配状态取反，得到一个更大的匹配 S'。
重复第二步，直至图中不存在增广路。

该算法的关键点在于如何找到一条增广路。匈牙利算法依次尝试给每一个左部节点 x 寻找一个匹配的右部节点 y。右部节点 y 能与左部节点 x 匹配，需要满足以下两个条件之一：

在程序中，我们一般使用深度优先遍历为框架，递归从 x 点出发找增广路。若找到，则在深搜回溯时，正好把路径上的匹配状态取反。另外，定义一个标记数组，记录节点的访问情况，避免重复搜索。

同学们可以自己画一下图，我这边使用的是《算法竞赛进阶指南》里的图。

匈牙利算法的正确性基于贪心策略，它的一个重要特点是：当一个节点成为匹配点后，至多因为找到增广路而更换匹配对象，但是绝对不会再变回原匹配点。

对于每个左部节点，寻找增广路最多遍历整张二分图一次。因此，该算法的时间复杂度为 O(NM)。

我们来写一下代码：

//...

bool dfs(int u)
{
    for (int i = pre[u]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!vis[to])
        {
            vis[to] = true;
            if (!match[to] || dfs(match[to]))
            {
                match[to] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    // ...
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof vis);
        ans += dfs(i);
    }
    // ...
    return 0;
}

理解了以后，我们来做几道例题。

二分图最大匹配例题

P3386 【模板】二分图最大匹配
P1894 [USACO4.2] 完美的牛栏 The Perfect Stall
P10936 导弹防御塔
P10937 車的放置

例题讲解

注：有问题可私信问或者在评论区里问

第一题：P3386 【模板】二分图最大匹配

这道题就是纯模板，使用链式前向星建边（个人习惯，不喜勿喷），然后直接套用我刚刚写的匈牙利算法代码就搞定了。

然后我们来写一下代码：

#include <bits/stdc++.h>
#define N 500005
using namespace std;
int n, m, e, u, v, pre[N], k = 0, match[N];
bool vis[N];
struct Edge
{
    int to, ne;
} a[N];
void add(int u, int v)
{
    a[++k] = (Edge){v, pre[u]};
    pre[u] = k;
}
bool dfs(int x)
{
    for (int i = pre[x]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!vis[to])
        {
            vis[to] = true;
            if (!match[to] || dfs(match[to]))
            {
                match[to] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++)
    {
        cin >> u >> v;
        add(u, v);
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof vis);
        res += dfs(i);
        // if (dfs(i))
        //     res++;
    }
    cout << res;
    return 0;
}

第二题：P1894 [USACO4.2] 完美的牛栏 The Perfect Stall

这道题其实和上一道题差不多，只是在建边的时候变了一下。其它的就不多说了，我们直接上代码！

#include <bits/stdc++.h>
#define N 500005
using namespace std;
int n, m, e, u, v, pre[N], k = 0, match[N];
bool vis[N];
struct Edge
{
    int to, ne;
} a[N];
void add(int u, int v)
{
    a[++k] = (Edge){v, pre[u]};
    pre[u] = k;
}
bool dfs(int x)
{
    for (int i = pre[x]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!vis[to])
        {
            vis[to] = true;
            if (!match[to] || dfs(match[to]))
            {
                match[to] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> e;
        for (int j = 1; j <= e; j++)
        {
            cin >> u;
            add(i, u);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof vis);
        res += dfs(i);
        // if (dfs(i))
        //     res++;
    }
    cout << res;
    return 0;
}

第三题：P10936 导弹防御塔

这道题就有难度了，建议看完分析再做。

如果时间较短时能击退入侵者，那么时间较长时也能击退入侵者，显然，本题具有单调性。我们使用二分答案，设当前二分的中值为击退时间，我们就可以把问题转化为“能否在当前击退时间（当前二分中值）之内击退所有入侵者”。

首先我们要注意：每个入侵者被攻击一次后就会死，虽然每个塔台可以发射多枚导弹，但是，一个导弹只能击退一个入侵者。（~~这入侵者也太弱了 qwq~~

已知，发射预热时间 T_1、冷却时间 T_2，我们容易计算出每座塔在当前二分的击退时间内至多能够发射多少枚导弹，我们将它记为 P。经过分析，我们容易发现，这道题是一个多重匹配问题，我们可以把入侵者看作二分图的左部节点，把每座塔台拆成 P 个导弹，作为二分图的右部节点。最终，共有 M 个左部节点，和 N \times P 个右部节点。

注意，因为塔台和入侵者的坐标各不相同，所以导弹飞到飞到入侵者的时间也可能不同。我们在连边时，还需要检查导弹是否有足够的时间飞到入侵者。因此，一座塔台的 P 个导弹是不等价的，这个多重匹配问题必须使用拆点的方法解决。如果在当前二分中值时间内，第 i(1 \leq i \leq M) 个入侵者能够被第 j(1 \leq j \leq N) 座塔台的第 k(1 \leq k \leq P) 个导弹击中，那么，在第 i 个左部节点和第 (j - 1) \times P + K 个右部节点之间连一条无向边。

用匈牙利算法计算该二分图的最大匹配。若每个左部节点都能找到匹配节点，说明能够在当前二分中值的时间内击退所有入侵者，就令二分上界为当前中值，否则令二分下界为二分中值加一。

最后附上代码：

#include <bits/stdc++.h>
#define int long long
#define N 3005
using namespace std;
const double M = 1e-5;
struct node
{
    double x, y;
} a[N], b[N];
vector<int> g[N];
int match[N], n, m, vis[N];
double t1, t2, v;
bool dfs(int x, int tag)
{
    if (vis[x] == tag)
        return 0;
    vis[x] = tag;
    for (auto to : g[x])
        if (!match[to] || dfs(match[to], tag))
        {
            match[to] = x;
            return true;
        }
    return false;
}
bool check(double mid)
{
    memset(match, 0, sizeof match);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= m; i++)
        g[i].clear();
    int num = min(m, max(0ll, (int)floor((mid + t2) / (t1 + t2))));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= num; k++)
            {
                double tmp = sqrt(pow(b[i].x - a[j].x, 2) + pow(b[i].y - a[j].y, 2)) / v + (k - 1) * 1.00 * (t1 + t2) + t1;
                if (tmp > mid)
                    continue;
                g[i].push_back((j - 1) * num + k);
            }
    for (int i = 1; i <= m; i++)
        if (!dfs(i, i))
            return false;
    return true;
}
signed main()
{
    cin >> n >> m >> t1 >> t2 >> v;
    t1 /= 60.00;
    for (int i = 1; i <= m; i++)
        cin >> b[i].x >> b[i].y;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    double l = 0, r = 1e9;
    while (l + M < r)
    {
        double mid = (l + r) / 2.00;
        if(check(mid)) r = mid;
        else l = mid;
    }
    printf("%.6lf", l);
    return 0;
}

第四题：P10937 車的放置

看了上面的分析，其实做这道题就很容易了，分析我就不多说了（欢迎把分析打在评论里）。直接附上代码：

#include <bits/stdc++.h>
#define N 500005
#define wzx 205
using namespace std;
int n, m, e, u, v, pre[N], k = 0, match[N];
bool mp[wzx][wzx];
bool vis[N];
struct Edge
{
    int to, ne;
} a[N];
void add(int u, int v)
{
    a[++k] = (Edge){v, pre[u]};
    pre[u] = k;
}
bool dfs(int x)
{
    for (int i = pre[x]; i; i = a[i].ne)
    {
        int to = a[i].to;
        if (!vis[to])
        {
            vis[to] = 1;
            if (!match[to] || dfs(match[to]))
            {
                match[to] = x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++)
    {
        cin >> u >> v;
        mp[u][v] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!mp[i][j])
                add(i, j);
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof vis);
        res += dfs(i);
        // if (dfs(i))
        //     res++;
    }
    cout << res;
    return 0;
}

后记

这篇专栏就到此结束了，接下来我会更新二分图带权匹配、网络流等知识。