跳转至

二分图最大匹配

为了描述方便将两个集合分成左和右两个部分,所有匹配边都是横跨左右两个集合,可以假想成男女配对。

假设图有 \(n\) 个顶点,\(m\) 条边。

题目描述

给定一个二分图 \(G\),即分左右两部分,各部分之间的点没有边连接,要求选出一些边,使得这些边没有公共顶点,且边的数量最大。

增广路算法 Augmenting Path Algorithm

因为增广路长度为奇数,路径起始点非左即右,所以我们先考虑从左边的未匹配点找增广路。 注意到因为交错路的关系,增广路上的第奇数条边都是非匹配边,第偶数条边都是匹配边,于是左到右都是非匹配边,右到左都是匹配边。 于是我们给二分图 定向,问题转换成,有向图中从给定起点找一条简单路径走到某个未匹配点,此问题等价给定起始点 \(s\) 能否走到终点 \(t\)。 那么只要从起始点开始 DFS 遍历直到找到某个未匹配点,\(O(m)\)。 未找到增广路时,我们拓展的路也称为 交错树

性质

因为要枚举 \(n\) 个点,总复杂度为 \(O(nm)\)

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct augment_path {
  vector<vector<int> > g;
  vector<int> pa;  // 匹配
  vector<int> pb;
  vector<int> vis;  // 访问
  int n, m;         // 两个点集中的顶点数量
  int dfn;          // 时间戳记
  int res;          // 匹配数

  augment_path(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    vis = vector<int>(n);
    g.resize(n);
    res = 0;
    dfn = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int v) {
    vis[v] = dfn;
    for (int u : g[v]) {
      if (pb[u] == -1) {
        pb[u] = v;
        pa[v] = u;
        return true;
      }
    }
    for (int u : g[v]) {
      if (vis[pb[u]] != dfn && dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      dfn++;
      int cnt = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          cnt++;
        }
      }
      if (cnt == 0) {
        break;
      }
      res += cnt;
    }
    return res;
  }
};

转为网络最大流模型

二分图最大匹配可以转换成网络流模型。

将源点连上左边所有点,右边所有点连上汇点,容量皆为 \(1\)。原来的每条边从左往右连边,容量也皆为 \(1\),最大流即最大匹配。

如果使用 Dinic 算法 求该网络的最大流,可在 \(O(\sqrt{n}m)\) 求出。

Dinic 算法分成两部分,第一部分用 \(O(m)\) 时间 BFS 建立网络流,第二步是 \(O(nm)\) 时间 DFS 进行增广。

但因为容量为 \(1\),所以实际时间复杂度为 \(O(m)\)

接下来前 \(O(\sqrt{n})\) 轮,复杂度为 \(O(\sqrt{n}m)\)\(O(\sqrt{n})\) 轮以后,每条增广路径长度至少 \(\sqrt{n}\),而这样的路径不超过 \(\sqrt{n}\),所以此时最多只需要跑 \(\sqrt{n}\) 轮,整体复杂度为 \(O(\sqrt{n}m)\)

代码可以参考 Dinic 算法 的参考实现,这里不再给出。

补充

二分图最小点覆盖(König 定理)

最小点覆盖:选最少的点,满足每条边至少有一个端点被选。

二分图中,最小点覆盖 \(=\) 最大匹配。

证明

将二分图点集分成左右两个集合,使得所有边的两个端点都不在一个集合。

考虑如下构造:从左侧未匹配的节点出发,按照匈牙利算法中增广路的方式走,即先走一条未匹配边,再走一条匹配边。由于已经求出了最大匹配,所以这样的增广路一定以匹配边结束。在所有经过这样「增广路」的节点上打标记。则最后构造的集合是:所有左侧未打标记的节点和所有右侧打了标记的节点。

首先,易证这个集合的大小等于最大匹配。打了标记的节点一定都是匹配边上的点,一条匹配的边两侧一定都有标记(在增广路上)或都没有标记,所以两个节点中必然有一个被选中。

其次,这个集合是一个点覆盖。一条匹配边一定有一个点被选中,而一条未匹配的边一定是增广路的一部分,而右侧端点也一定被选中。

同时,不存在更小的点覆盖。为了覆盖最大匹配的所有边,至少要有最大匹配边数的点数。

二分图最大独立集

最大独立集:选最多的点,满足两两之间没有边相连。

因为在最小点覆盖中,任意一条边都被至少选了一个顶点,所以对于其点集的补集,任意一条边都被至多选了一个顶点,所以不存在边连接两个点集中的点,且该点集最大。因此二分图中,最大独立集 \(=n-\) 最小点覆盖。

习题

UOJ #78. 二分图最大匹配

模板题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

struct augment_path {
  vector<vector<int> > g;
  vector<int> pa;  // 匹配
  vector<int> pb;
  vector<int> vis;  // 访问
  int n, m;         // 顶点和边的数量
  int dfn;          // 时间戳记
  int res;          // 匹配数

  augment_path(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    vis = vector<int>(n);
    g.resize(n);
    res = 0;
    dfn = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int v) {
    vis[v] = dfn;
    for (int u : g[v]) {
      if (pb[u] == -1) {
        pb[u] = v;
        pa[v] = u;
        return true;
      }
    }
    for (int u : g[v]) {
      if (vis[pb[u]] != dfn && dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      dfn++;
      int cnt = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          cnt++;
        }
      }
      if (cnt == 0) {
        break;
      }
      res += cnt;
    }
    return res;
  }
};

int main() {
  int n, m, e;
  cin >> n >> m >> e;
  augment_path solver(n, m);
  int u, v;
  for (int i = 0; i < e; i++) {
    cin >> u >> v;
    u--, v--;
    solver.add(u, v);
  }
  cout << solver.solve() << "\n";
  for (int i = 0; i < n; i++) {
    cout << solver.pa[i] + 1 << " ";
  }
  cout << "\n";
}
P1640 [SCOI2010] 连续攻击游戏

None

Codeforces 1139E - Maximize Mex

None

参考资料

  1. http://www.matrix67.com/blog/archives/116