二分圖最大匹配

為了描述方便將兩個集合分成左和右兩個部分，所有匹配邊都是橫跨左右兩個集合，可以假想成男女配對。

假設圖有 \(n\) 個頂點，\(m\) 條邊。

題目描述

給定一個二分圖 \(G\)，即分左右兩部分，各部分之間的點沒有邊連接，要求選出一些邊，使得這些邊沒有公共頂點，且邊的數量最大。

增廣路算法 Augmenting Path Algorithm

因為增廣路長度為奇數，路徑起始點非左即右，所以我們先考慮從左邊的未匹配點找增廣路。注意到因為交錯路的關係，增廣路上的第奇數條邊都是非匹配邊，第偶數條邊都是匹配邊，於是左到右都是非匹配邊，右到左都是匹配邊。於是我們給二分圖定向，問題轉換成，有向圖中從給定起點找一條簡單路徑走到某個未匹配點，此問題等價給定起始點 \(s\) 能否走到終點 \(t\)。那麼只要從起始點開始 DFS 遍歷直到找到某個未匹配點，\(O(m)\)。未找到增廣路時，我們拓展的路也稱為 交錯樹。

性質

因為要枚舉 \(n\) 個點，總複雜度為 \(O(nm)\)。

實現

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. 二分圖最大匹配

模板題

#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

參考資料

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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：accelsao, thallium, Chrogeek, Enter-tainer, ksyx, StudyingFather, H-J-Granger, Henry-ZHR, countercurrent-time, william-song-shy, 5ab-juruo, XiaoQuQuSD
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用