一般圖最大權匹配

本頁從一般圖最大權完美匹配到一般圖最大權匹配（最大權匹配可以通過增加零邊變成最大權完美匹配）。

預備知識

花（blossom）

一般圖匹配和二分圖匹配不同的是，圖可能存在奇環。可以將偶環視為二分圖。

帶花樹算法（Blossom Algorithm）的處理方式時是遇到奇環就把它縮成一個 花（Blossom），並把花中所有的點設為偶點。既然花上的點都可以成為偶點，那麼可以把整個花直接縮成一個偶點。注意，一個花可以包含其它花。

這也可以變成線性規劃和對偶問題，但是要對花進行一些處理。

頂標（vertex labeling）和等邊（Equality Edge）

定義 \(z_u\) 是點 \(u\) 的頂標（vertex labeling），與 \(KM\) 算法中定義的頂標含義相同。定義邊 \(e(u,v)\) 為 "等邊" 當且僅當點 \(u\) 和點 \(v\) 的標號和等於邊 \(e\) 的權值（\(z_u + z_v = w(e)\)），此時邊的標號 \(z_e = z_u + z_v − w(e) = 0\)。

一般圖最大權完美匹配的線性規劃

定義

因為一朵花最少有三個點，縮花後成為一個點。設 \(O\) 為大小為 \(≥3\) 奇數的集合的集合（包含所有花），\(\gamma(S)\) 表示 \(S\) 集合中的邊。

\[ \begin{aligned} & \text{設} S\subseteq V \\ & \gamma(S)=\{(u,v)\in E:u\in S,v\in S\} \\ & O=\{B\subseteq V:|B|\text{是奇數且}|B|\geq3\} \\ \end{aligned} \]

對偶問題

原問題

\[ \begin{aligned} & \max\sum_{e\in E}w(e)x_e \\ & \text{限制：} \\ & x(\delta(u))=1:\forall u\in V \\ & x(\gamma(B))\leq\lfloor\frac{|B|}{2}\rfloor:\forall B\in O \\ & x_e\geq0:\forall e\in E \\ \end{aligned} \]

然後通過原始對偶（Primal-Dual）將問題轉換為對偶問題。

對偶問題

\[ \begin{aligned} & \min\sum_{u\in V}z_u+\sum_{B\in O}\left\lfloor\frac{|B|}{2}\right\rfloor z_B \\ & \text{限制：} \\ & z_B\geq0:\forall B\in O \\ & z_e\geq0:\forall e\in E \\ & \text{設} e=(u,v)，\text{這裏} \\ & \begin{array}{lll} z_e & = & z_u + z_v - w(e) + \sum_{\substack{B \in O \\ u,v \in \gamma(B)}} z_B \end{array} \end{aligned} \]

\(x_e=1\) 的邊是匹配邊，\(x_e=0\) 的邊是非匹配邊。和二分圖一樣，我們必須滿足 \(x_e\in\{0,1\}:\forall e\in E\)。因此必須在最大權完美匹配的時候，讓所有匹配邊都是等邊的。

和二分圖不同的是，一般圖多了 \(z_B\) 要處理。下面考慮 \(z_B\) 什麼時候大於 \(0\)。

可以看出，儘量使 \(z_B=0\) 是最好的做法，但在不得已時還是要讓 \(z_B>0\)。在 \(x(\gamma(B)) = \left\lfloor \dfrac{|B|}2 \right\rfloor \text{且} x(\delta(B)) = 1\) 時，讓 \(z_B>0\) 即可。因為除了在這種情況下，\(z_B>0\) 是無意義的。

根據互補鬆弛條件，有以下的對應關係：

對於選中的邊 \(e\)，必有 \(z_e=0\)。

\[ x_e>0 \longrightarrow z_e=0,\quad \forall e\in E \]
對於選中的集合B，\(z_B>0 \longrightarrow x(\gamma(B))= \left\lfloor \dfrac{|B|}2 \right\rfloor\)，即所有 \(z_B>0\) 的集合 \(B\)，都被選了集合大小一半的邊，也即集合 \(B\) 是一朵花，選中花中的一條邊進行增廣。同時，我們加入一個條件：\(x(\delta(B))=1\)，即只有花 \(B\) 向外連了一條邊的時候，\(z_B>0\) 才是有意義的。

\[ z_B>0 \longrightarrow x(\gamma(B))=\left\lfloor\frac{|B|}2\right\rfloor, x(\delta(B))=1\quad \forall B\in O \]

以「等邊」的概念，結合之前的帶花樹算法：用「等邊」構成的增廣路不斷進行擴充，由於用來擴充的邊全是「等邊」，最後得到的最大權完美匹配仍然全是「等邊」。

處理花的問題

當遇到花的時候，要將它縮成一個偶點。將花中所有點都設為偶點，並讓它的 \(z_B=0\)。

由於縮花後會把花保存起來，直到滿足某些條件才會拆開，所以不能用之前的方法記錄花。

如果沒有特殊説明，之前提到的點，都包含縮花形成的偶點。

由於花也有可能縮成點被加入隊列中，並且花的數量是不固定的，因此不能像之前一樣枚舉每個點來檢查是否有增廣路。因此，在進行廣度優先搜索（BFS）時，必須將所有未匹配的點都放入隊列中。

這樣會同時產生很多棵交錯樹。

算法的四個步驟

這個算法可以分成四個步驟。

GROW（等邊）：用 "等邊" 構成交錯樹。
AUGMENT（增廣）：找出增廣路並擴充匹配。
SHRINK（縮花）：把花縮成一個點。
EXPAND（展開）：把花拆開。

general-weight-match-1

在 AUGMENT 階段時，因為所有未匹配點都會在不同的交錯樹上，所以當增廣時兩棵交錯樹的偶點連在一起，就表示找到了一條增廣路。

找不到等邊擴充

和二分圖一樣，也會有找不到「等邊」擴充的問題。這時就需要調整 vertex labeling。

調整 VERTEX LABELING

vertex labeling 仍要維持大於等於的性質，而且既有的「等邊」不能被改變，還要讓 \(z_B\) 儘量的小。

定義符號奇偶點

以 \(u^−\) 來表示 \(u\) 在交錯樹上為奇點。
以 \(u^+\) 來表示 \(u\) 在交錯樹上為偶點。
以 \(u^\varnothing\) 來表示 \(u\) 不在任何一棵交錯樹上。
之後所有提到的 \(B\) 預設都是花，並同時代表縮花之後的點。
花也可以有奇花偶花之分，因此也適用 \(B^+\)、\(B^−\)、\(B^\varnothing\) 等符號。

設目前有 r 棵交錯樹 \(T_i=(U_{t_i},V_{t_i}):1\leq i\leq r\)，令

\[ \begin{aligned} d1 &= \min(\{z_e : e = (u^+,v^\varnothing)\}) \\ d2 &= \min(\{z_e : e = (u^+,v^+), ~ u^+ \in T_i, ~ v^+ \in T_j, ~ i \neq j\}) / 2 \\ d3 &= \min(\{z_{B^-} : B^- \in O\}) / 2 \end{aligned} \]

注意這裏B是縮花之後的點，所以可以有奇偶性。

設 \(d=min(d1,d2,d3)\)，讓

\[ \begin{aligned} z_{u^+} - &= d \\ z_{v^-} + &= d \\ z_{B^+} + &= 2d \\ z_{B^-} - &= 2d \\ \end{aligned} \]

如果出現 \(z_B=0(d=d3)\)，為了防止 \(z_B<0\) 的情況，所以要把這朵花拆了 (EXPAND)。拆花後只留下花裏的交替路徑，並把花裏不在交替路徑上的點設為未走訪 (\(\varnothing\))。

如此便製造了一條（以上）的等邊，既有等邊保持不動，並維持了 \(z_e\geq0:\forall e\in E\) 的性質，且最低限度增加了 \(z_B\)，可以繼續找增廣路了。

一般圖最大權匹配

以上求的是最大權完美匹配，求最大權匹配需要在 vertex labeling 額外增加一個限制：對於所有匹配點 \(u\)，\(z_u>0\)。

開始時先設所有的 \(z_u=max(\{w(e):e\in E\})/2\)。

vertex labeling 為 \(0\) 的點最後將成為未匹配點。

參考代碼

這裏為了方便實現，使用邊權乘 \(2\) 來計算 \(z_e\) 的值，這樣就不會出現浮點數誤差了。

存儲

#define INF INT_MAX
#define MAXN 400

struct edge {
  int u, v, w;

  // 表示(u,v)為一條邊其權重為w
  edge() {}

  edge(int u, int v, int w) : u(u), v(v), w(w) {}
};

int n, n_x;
// 有n個點，編號為 1 ~ n
// n_x表示當前點加上花的數量，編號從n+1到n_x為花的節點
edge g[MAXN * 2 + 1][MAXN * 2 + 1];
// 圖用鄰接矩陣存儲，因為最多有n-1朵花，所以大小為MAXN*
vector<int> flower[MAXN * 2 + 1];
// flower[b]記錄了花b中有哪些點
// 我們記錄花中的點的方式是隻記錄花裏面的最外層花

下面是嵌套花的例子。

general-weight-match-2

其中 \(\{ 6, 5, 8\} \in b1,\{ b1, 4, 3, 2, 11, 10, 9\} \in b2\)。存儲為：

flower[b2] = {b1, 4, 3, 2, 11, 10, 9} 
flower[b1] = {6, 5, 8}

general-weight-match-3

flower[b2] = {9, b1, 4, 3, 2, 11, 10} 
flower[b1] = {5, 8, 6}

int lab[MAXN * 2 + 1];
// lab[u]用來記錄z_u, lab[b]用來記錄z_B
int match[MAXN * 2 + 1], slack[MAXN * 2 + 1], st[MAXN * 2 + 1],
    pa[MAXN * 2 + 1];
// match[x]=y表示(x,y)是匹配，這裏x、y可能是花
// slack[x]=u表示z(x,u)是所有和x相鄰的邊中最小的那條邊
// 表示節點 x 所在的花是 b。如果 x=b 且 b<=n，則表示 x
// 是一個普通節點（不屬於任何花） 表示在交錯樹中，節點 v 的父節點是 u
int flower_from[MAXN * 2 + 1][MAXN + 1], S[MAXN * 2 + 1], vis[MAXN * 2 + 1];
/*
flower_from[b][x]=xs表示最大的包含x的b的子花是xs
x是b裏面的一個點，xs是b裏面的一朵花或一個點，同時x=xs或x是xs的其中一個點
*/
// S[u]={-1:沒走過 0:偶點 1:奇點}
// vis只用在找lca的時候檢查是不是走過了
queue<int> q;
// BFS找增廣路用的queue

general-weight-match-4

flower_from[b2][6] = b1 
flower_from[b2][5] = b1 
flower_from[b2][9] = 9 
flower_from[b1][6] = 6 
以此類推

inline int e_delta(const edge &e) {
  // 計算ze，為了方便起見先把所有邊的權重乘二
  // 在花裏面直接計算 e_delta 值會導致錯誤
  return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2;
}

inline void update_slack(int u, int x) {
  // 以u更新slack[x]的值
  if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) {
    slack[x] = u;
  }
}

inline void set_slack(int x) {
  // 算出slack[x]的值，slack[x]=0表示x是交錯樹中的節點
  slack[x] = 0;
  for (int u = 1; u <= n; ++u) {
    if (g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) {
      update_slack(u, x);
    }
  }
}

void q_push(int x) {
  // 把x丟到queue裏面，我們設定queue不能直接push一朵花
  if (x <= n)
    q.push(x);
  else {
    // 若要push花必須將花裏面原圖的點都添加到queue中
    for (size_t i = 0; i < flower[x].size(); i++) {
      q_push(flower[x][i]);
    }
  }
}

inline void set_st(int x, int b) {
  // 將x所在的花設為b
  st[x] = b;
  if (x > n) {
    // 若x也是花的話，就必須要把x裏面的點其所在的花也設為b
    for (size_t i = 0; i < flower[x].size(); ++i) {
      set_st(flower[x][i], b);
    }
  }
}

inline int get_pr(int b, int xr) {
  // xr是flower[b]中的一個點，返回值pr是它的位置
  // 為了方便程序運行，我們讓 flower[b][0]~flower[b][pr]為花裏的交替路
  int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin();
  if (pr % 2 == 1) {
    // 檢查他在花裏的位置，如果 flower[b][0]~flower[b][pr] 不是交替路
    // 就把整朵花反轉，重新計算 pr
    // 讓 flower[b][0]~flower[b][pr] 為花裏的交替路
    reverse(flower[b].begin() + 1, flower[b].end());
    return (int)flower[b].size() - pr;
  } else
    return pr;
}

general-weight-match-5

如果使用 get_pr(b2,11)，flower[b2] 會變成 {9,10,11,2,3,4,b1}，並返回 2。

如果使用 get_pr(b2,2)，flower[b2] 會變成 {9,b1,4,3,2,11,10}，並返回 4。

inline void set_match(int u, int v) {
  // 設置u和v為匹配邊，u和v有可能是花
  match[u] = g[u][v].v;
  if (u > n) {
    // 如果u是花的話
    edge e = g[u][v];
    int xr = flower_from[u][e.u];  // 找出e.u在flower[u]裏的哪朵花上
    int pr = get_pr(u, xr);  // 找出xr的位置並讓0~pr為花裏的交替路徑
    for (int i = 0; i < pr; ++i) {  // 把花裏的交替路上的匹配邊和非匹配邊反轉
      set_match(flower[u][i], flower[u][i ^ 1]);
    }
    set_match(xr, v);  // 設置(xr,v)為匹配邊
    rotate(flower[u].begin(), flower[u].begin() + pr, flower[u].end());
    // 最後把pr設為花托，因為花的存法是flower[u][0]會是u的花托
    // 所以要把flower[u][pr] rotate 到最前面
  }
}

inline void augment(int u, int v) {
  // 把u和u的祖先全部增廣，並設(u,v)為匹配邊
  for (;;) {
    int xnv = st[match[u]];
    set_match(u, v);
    if (!xnv) return;
    set_match(xnv, st[pa[xnv]]);
    u = st[pa[xnv]];
    v = xnv;
  }
}

inline int get_lca(int u, int v) {
  // 找出u,v在交錯樹上的lca
  static int t = 0;
  for (++t; u || v; swap(u, v)) {
    if (u == 0) continue;
    if (vis[u] == t) return u;
    vis[u] = t;  // 這種方法可以不用清空vis數組
    u = st[match[u]];
    if (u) u = st[pa[u]];
  }
  return 0;
}

增加一朵奇花

inline void add_blossom(int u, int lca, int v) {
  // 將u,v,lca這朵花縮成一個點 b
  // 交錯樹上u,v的lca即為花托
  int b = n + 1;
  while (b <= n_x && st[b]) ++b;
  if (b > n_x) ++n_x;
  // 找出目前未使用的花的編號
  lab[b] = 0;             // 設置zB=0
  S[b] = 0;               // 整朵花為一個偶點
  match[b] = match[lca];  // 設置花的匹配邊為花托的匹配邊
  flower[b].clear();
  flower[b].push_back(lca);
  for (int x = u, y; x != lca; x = st[pa[y]]) {
    flower[b].push_back(x);
    y = st[match[x]];
    flower[b].push_back(y);
    q_push(y);
  }
  reverse(flower[b].begin() + 1, flower[b].end());
  for (int x = v, y; x != lca; x = st[pa[y]]) {
    flower[b].push_back(x);
    y = st[match[x]];
    flower[b].push_back(y);
    q_push(y);
  }
  // b中所有點以環形的方式加入flower[b]，並設花托為首個元素
  set_st(b, b);  // 把整朵花裏所有的元素其所在的花設為b
  for (int x = 1; x <= n_x; ++x) {
    g[b][x].w = 0;
    g[x][b].w = 0;
  }
  for (int x = 1; x <= n; ++x) {
    flower_from[b][x] = 0;
  }
  for (size_t i = 0; i < flower[b].size(); ++i) {
    int xs = flower[b][i];
    for (int x = 1; x <= n_x; ++x) {
      // 設置b和x相鄰的邊為b裏面和x相鄰的邊e_delta最小的那條
      if (g[b][x].w == 0 || e_delta(g[xs][x]) < e_delta(g[b][x])) {
        g[b][x] = g[xs][x];
        g[x][b] = g[x][xs];
      }
    }
    for (int x = 1; x <= n; ++x) {
      if (flower_from[xs][x]) {
        // 如果b裏面的點xs有包含x
        // 那flower_from[b][x]就會是xs
        flower_from[b][x] = xs;
      }
    }
  }
  set_slack(b);
  // 最後必須要設置b的slack值
}

拆花

inline void expand_blossom(int b) {
  // b是奇花且zB=0時，必須要把b拆開
  // 因為只拆開b而已，所以如果b裏面有包含其他的花
  // 不需要把他們拆開
  for (size_t i = 0; i < flower[b].size(); ++i) {
    set_st(flower[b][i], flower[b][i]);
    // 先把flower[b]裏每個元素所在的花設為自己
  }
  int xr = flower_from[b][g[b][pa[b]].u];
  // xr表示交錯路上b的父母節點在flower[b]裏的哪朵花上
  int pr = get_pr(b, xr);  // 找出xr的位置並讓0~pr為花裏的交替路徑
  for (int i = 0; i < pr; i += 2) {
    // 把交替路徑拆開到交錯樹中
    // 並把交替路中的偶點丟到queue裏
    int xs = flower[b][i];
    int xns = flower[b][i + 1];
    pa[xs] = g[xns][xs].u;
    S[xs] = 1;
    S[xns] = 0;
    slack[xs] = 0;
    set_slack(xns);
    q_push(xns);
  }
  S[xr] = 1;  // 這時xr會是奇點或奇花
  pa[xr] = pa[b];
  for (size_t i = pr + 1; i < flower[b].size(); ++i) {
    // 把花中所有不再交替路徑上的點設為未走訪
    int xs = flower[b][i];
    S[xs] = -1;
    set_slack(xs);
  }
  st[b] = 0;
}

嘗試增廣一條等邊

inline bool on_found_edge(const edge &e) {
  // BFS時找到一條等邊e
  // 要對它進行以下的處理
  // 這裏u一定是偶點
  int u = st[e.u], v = st[e.v];
  if (S[v] == -1) {
    // v是未走訪節點
    pa[v] = e.u;
    S[v] = 1;
    int nu = st[match[v]];
    slack[v] = 0;
    slack[nu] = 0;
    S[nu] = 0;
    q_push(nu);
  } else if (S[v] == 0) {
    // v是偶點
    int lca = get_lca(u, v);
    if (!lca) {  // lca=0表示u,v在不同的交錯樹上，有增廣路
      augment(u, v);
      augment(v, u);
      return true;  // 找到增廣路
    } else
      add_blossom(u, lca, v);
    // 否則u,v在同棵樹上就會是一朵花，要縮花
  }
  return false;
}

增廣

inline bool matching() {
  memset(S + 1, -1, sizeof(int) * n_x);
  memset(slack + 1, 0, sizeof(int) * n_x);
  q = queue<int>();  // 把queue清空
  for (int x = 1; x <= n_x; ++x) {
    if (st[x] == x && !match[x]) {
      // 把所有非匹配點加入queue裏面，並設為偶點
      pa[x] = 0;
      S[x] = 0;
      q_push(x);
    }
  }
  if (q.empty()) return false;  // 所有點都有匹配了
  for (;;) {
    while (q.size()) {
      // BFS
      int u = q.front();
      q.pop();
      if (S[st[u]] == 1) continue;
      for (int v = 1; v <= n; ++v) {
        if (g[u][v].w > 0 && st[u] != st[v]) {
          if (e_delta(g[u][v]) == 0) {
            if (on_found_edge(g[u][v])) return true;
          } else
            update_slack(u, st[v]);
        }
      }
    }
    // 修改lab值
    int d = INF;
    for (int u = 1; u <= n; ++u) {
      // 這是為了防止出現lab<0的情況發生
      // 只要有任何一個lab[u]=0就結束程序
      if (S[st[u]] == 0) d = min(d, lab[u]);
    }
    for (int b = n + 1; b <= n_x; ++b) {
      if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
    }
    for (int x = 1; x <= n_x; ++x)
      if (st[x] == x && slack[x]) {
        if (S[x] == -1)
          d = min(d, e_delta(g[slack[x]][x]));
        else if (S[x] == 0)
          d = min(d, e_delta(g[slack[x]][x]) / 2);
      }
    for (int u = 1; u <= n; ++u) {
      if (S[st[u]] == 0) {
        if (lab[u] == d) return 0;
        // 如果lab[u]=0就直接結束程序
        lab[u] -= d;
      } else if (S[st[u]] == 1)
        lab[u] += d;
    }
    for (int b = n + 1; b <= n_x; ++b) {
      if (st[b] == b) {
        if (S[st[b]] == 0)
          lab[b] += d * 2;
        else if (S[st[b]] == 1)
          lab[b] -= d * 2;
      }
    }
    q = queue<int>();  // 把queue清空
    for (int x = 1; x <= n_x; ++x) {
      // 檢查看看有沒有增廣路徑產生
      if (st[x] == x && slack[x] && st[slack[x]] != x &&
          e_delta(g[slack[x]][x]) == 0)
        if (on_found_edge(g[slack[x]][x])) return true;
    }
    for (int b = n + 1; b <= n_x; ++b) {
      // EXPAND的操作，把所有lab[b]=0的奇花拆開
      if (st[b] == b && S[b] == 1 && lab[b] == 0) expand_blossom(b);
    }
  }
  return false;
}

主函數

inline pair<long long, int> weight_blossom() {
  // 主函數，一開始先初始化
  memset(match + 1, 0, sizeof(int) * n);
  n_x = n;  // 一開始沒有花
  int n_matches = 0;
  long long tot_weight = 0;
  for (int u = 0; u <= n; ++u) {
    // 先把自己所在的花設為自己
    st[u] = u;
    flower[u].clear();
  }
  int w_max = 0;
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v) {
      // u是一個點時，裏面所包含的點只有自己
      flower_from[u][v] = (u == v ? u : 0);
      w_max = max(w_max, g[u][v].w);
      // 找出最大的邊權
    }
  for (int u = 1; u <= n; ++u) lab[u] = w_max;
  // 讓所有的lab=最大的邊權
  // 因為這裏實現是用邊權乘二來計算ze的值所以不用除以二
  while (matching()) ++n_matches;
  for (int u = 1; u <= n; ++u)
    if (match[u] && match[u] < u) tot_weight += g[u][match[u]].w;
  return make_pair(tot_weight, n_matches);
}

初始化

很重要使用前一定要初始化

inline void init_weight_graph() {
  // 在把邊輸入到圖裏面前必須要初始化
  // 因為是最大權匹配所以把不存在的邊設為0
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v) g[u][v] = edge(u, v, 0);
}

複雜度分析

每朵花在一次 BFS 中只會被縮花或拆花一次。每次縮花或拆花的時間複雜度為 \(O(|V|)\)。最多總共有 \(O(|V|)\) 朵花，所以花的處理花費 \(O(|V|^2)\) 的時間。而 BFS 花費 \(O(|V| + |E|)\) 的時間複雜度。因此，找增廣路花費 \(O(|V| + |E|) + O(|V|^2) = O(|V|^2)\) 的時間複雜度。

最多做 \(|V|\) 次 BFS。所以，總時間複雜度為 \(O(|V|^3)\)。

習題

UOJ #81. 一般圖最大權匹配

參考資料

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：accelsao, Henry-ZHR, yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用