墨滴

小指针

V1

2022/09/30阅读：59主题：凝夜紫

【图论专题】二分图中最小覆盖问题的求解思路

最小点覆盖问题

「最小点覆盖」：给出一个图，从中选出最少的点，使得每一条边的两个点里面至少有一个点是被选出来的。

在「二分图中」，最小点覆盖有一个结论：「最小点覆盖数量==最大匹配数量」。

结论证明（可略过）

若想证明一个相等的结论，比如：「A==B」，我们可以先证明「A>=B」，再证明「A<=B」，这样就能推出来「A==B」，然而如果我们想求出来「A最小」，那么其实只需要证明「A>=B且A==B」，因为一定是取到等号的时候A才最小，所以我们就有本结论以下的证明方式：

  1. 最小点覆盖 >= 最大匹配数量

    这点可以从「定义」上来证明，最小点覆盖最终的目标是使得「所有的边中任意一条边」都有一个点被选出来，而最大匹配数量是从「所有的边中选择」出来匹配的，那么「选择」出来的一定是被包含在「所有边」中，所以有「最小点覆盖>=最大匹配数量」。

  2. 最小点覆盖 == 最大匹配数量

    这点可以使用「构造」的方式来证明。假设，我们能构造出来一个方案，恰好选择m（最大匹配数为m）条边，使得m条边「能够覆盖到所有的边」，因此，根据定义，「m就是最小点覆盖」，进而推出等号成立。

    如何构造呢？我们可以分为两步:

    1. 求最大匹配；
    2. 从左边每个非匹配点开始做增广。

求最大匹配

使用匈牙利算法，先求一次最大匹配的数量。其中白色线表示可匹配的边，红色表示匹配成功的边。

从左边每个非匹配点开始做增广

「从左边的每个非匹配点出发，做一遍增广，在过程中标记所有经过的点」（这个增广操作是一定会失败的，因为我们上一步已经求了一遍匈牙利算法，完成了所有可以成功的增广操作）。

最大匹配里的增广：对于这个概念还不熟悉的同学，请复习前置文章匈牙利算法，重点理解算法过程中的步骤3和4。

首先「左边2号点和4号点」是「非匹配点」。

「增广」步骤为，先从「左2号点」出发到达「右2号点」，再从「右2号点」到达「左1号点」，因此将这三个点用绿色圈标记起来；再从「左4号点」出发到达「右4号点」，然后从「右4号点」到达「左3号点」，因此再将这三个点用绿色圈标记出来。

「左边所有未被标记的点」 和 「右边所有被标记的点」 数量加起来就是一种「最小点覆盖」的方案（从图中可以直观的看到 最小点覆盖是3，因为右边1号点和3号点是孤立点，没有连接边）。

证明该方案符合最大匹配数量

那么，如何证明这种方案就是「最大匹配数量 m 呢」？

  1. 根据增广规则，「左部所有非匹配点，一定全部被标记」（因为他们都是起点）。

  2. 「右边所有的非匹配点，一定没有被标记」。因为如果右边的非匹配点被标记，那么就是一条新的匹配路径，但是，要知道「我们在证明的最初已经做了一遍匈牙利算法，从而求出来了所有的匹配边，因此不可能再存在新的匹配边」。

  3. 对于「所有的匹配边，边的两点必然 都被标记 或者 都没有被标记」。

  4. 注意，「还有一种隐含规则，不可能存在左右两个连接点，既没被标记，也没有匹配」，因为这种情况下，这两个点一定是可以匹配的，但是我们在第一步求最大匹配的时候，已经将所有匹配都找出来了。

综合上述三条性质，我们发现「左边所有未被标记的点一定是匹配点」（因为左边的非匹配点全部被标记到了）；「右边所有被标记的点一定是匹配点」（因为右边没被标记的点，一定是非匹配点）。

所以，我们按照上述规则选择的话，对于「任意一条匹配边，我们必然都只选择了一个点」。如果匹配边的两点被标记了，我们选择的就是右边，如果没被标记，我们选择的就是左边的点。

并且，我们所有选择的点，必然都是匹配边上的点，这就说明，我们「选择出来的所有匹配点的数量就是最大匹配(边)的数量」。

证明该方案是最小覆盖数量

我们再来看「不在匹配中的边」，可以分为两种情况：

  1. 左边的非匹配点 连接到 右边的匹配点（与上节的第三条矛盾）；

    已知左边的非匹配点 是被标记的，根据增广标记的规则，「被该点直接连接的右面点，一定也是被标记的」，而右面所有被标记的点都会被我们选择出来。所有这种情况下的非匹配边的右点一定被选择。

  2. 左边的匹配点 连接到 右边的非匹配点（与上节的第三条矛盾）；

    「左边的匹配点如果指向了右边的非匹配点，那么左边的匹配点一定不会被标记」，因为左匹配点在做增广时不是起点，如果它被标记了，一定是从右面过来的，那么从右面过来的那个点一定也被标记了，可是在上节，我们知道右面的非匹配点是不会被标记的。

所以，我们就用同样的方法（「左边所有未被标记的点」 和 「右边所有被标记的点」 数量加起来）构成了一种「最小点覆盖」的方案，该方案中如果边是匹配的，我们选择的点就是右面的，如果边是不匹配的，我们选择的点就是左面的，因此「满足所有的边都取一个点的」最小点覆盖定义。

因此，这种方法 既是最小点覆盖方案，又是最大匹配数量的方案，因此就可以推出「最小点覆盖 == 最大匹配数量」。

AcWing 376. 机器任务

有两台机器 A，B 以及 K 个任务。

机器 A 有 N 种不同的模式（模式 0∼N−1），机器 B 有 M 种不同的模式（模式 0∼M−1）。

两台机器最开始都处于模式 0。

每个任务既可以在 A 上执行，也可以在 B 上执行。

对于每个任务 i，给定两个整数 a[i] 和 b[i]，表示如果该任务在 A 上执行，需要设置模式为 a[i]，如果在 B 上执行，需要模式为 b[i]。

任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。

求怎样分配任务并合理安排顺序，能使机器重启次数最少。

「输入格式」
输入包含多组测试数据。

每组数据第一行包含三个整数 N,M,K。

接下来 K 行，每行三个整数 i,a[i] 和 b[i]，i 为任务编号，从 0 开始。

当输入一行为 0 时，表示输入终止。

「输出格式」
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。

「数据范围」

N,M<100,K<1000
0≤ a[i] < N
0≤ b[i] < M

「输入样例」

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0

「输出样例」

3

题目描述

有两台机器A和B，并且给出K个任务，再给出「两个数组a[i]和b[i]表示两个机器执行第i个任务需要使用的模式」，每转换一次模式机器就要重启动一次，问 「执行完K个任务最少需要重启多少次机器」。

题目分析

首先，题目中给出两个机器都从模式0开始，并且任务不必按照顺序执行，所以我们可以先把所有使用模式0执行的任务先全部完成（避免切换模式），所以剩下的任务都是大于0的。

因此问题就变成了在N+M-2（其中N和M是两种机器的模式数量）种模式中，最少选出多少个模式可以把所有剩余的任务完成。

如果我们「把a[i]和b[i]看成a[i]连向b[i]的一条有向边」，那么「完成任务i」就相当于是「在这条边上选择出一个点」。 如此，我们就把问题转换成了，在这个「二分图中」选择出最少的点，把所有的边覆盖到，也就是「最小点覆盖问题」，那么「二分图中的最小点覆盖问题 就等价于 最大匹配数量」，因此我们直接「使用匈牙利算法求出最大匹配数量」就是本题的答案。

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, K = 1010;
bool g[N][N], st[N];
int match[N];
int n, m, k;

// 匈牙利算法模板
int find(int u) {
    // 遍历集合b 用来找与u匹配的
    for (int i = 1; i < m; i ++ ) {
        // 如果 有边 并且b中的点没有被使用 则可以匹配
        if (g[u][i] and !st[i]) {
            st[i] = true;
            int t = match[i];
            // 如果点i没有匹配对象 或者 可以给它找到其他对象
            // 那么就把当前点u 匹配给它 
            // 所以当前点u就可以找到一个匹配对象
            if (t == -1 or find(t)) {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    while (cin >> n, n) {
        cin >> m >> k;
        // 多组数据 千万别忘记初始化
        memset(g, 0, sizeof g);
        memset(match, -1, sizeof match);
        while (k -- ) {
            int t, a, b;
            cin >> t >> a >> b;
            if (!a or !b) continue;
            g[a][b] = true;  // a[i] -> b[i] 之间有一条边
        }
        // 匈牙利算法模板
        int res = 0;
        // 遍历集合a 对于每个点都进行匹配
        for (int i = 1; i < n; i ++ ) {
            memset(st, 0, sizeof st);
            if (find(i)) res ++ ;
        }
        cout << res << endl;
    }
    return 0;
}

分类：

后端

标签：

数据结构与算法

作者介绍

小指针
V1