差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:lgwza:一般图最大匹配 [2020/08/19 23:55]
lgwza 创建
+++ 2020-2021:teams:legal_string:lgwza:一般图最大匹配 [2020/08/19 23:57] (当前版本)
lgwza
@@ 行 41: / 行 41: @@
 每次找增广路，遍历所有边，遇到 **花** 会维护 **花** 上的点，$O(|E|^2)$。枚举所有未匹配点做增广路，总共 $O(|V||E|^2)$。
+==== 代码 ====
+<hidden>
+<code cpp>
+// graph
+template <typename T>
+class graph {
+ public:
+  struct edge {
+    int from;
+    int to;
+    T cost;
+  };
+  vector<edge> edges;
+  vector<vector<int> > g;
+  int n;
+  graph(int _n) : n(_n) { g.resize(n); }
+  virtual int add(int from, int to, T cost) = 0;
+};
+// undirectedgraph
+template <typename T>
+class undirectedgraph : public graph<T> {
+ public:
+  using graph<T>::edges;
+  using graph<T>::g;
+  using graph<T>::n;
+  undirectedgraph(int _n) : graph<T>(_n) {}
+  int add(int from, int to, T cost = 1) {
+    assert(0 <= from && from < n && 0 <= to && to < n);
+    int id = (int)edges.size();
+    g[from].push_back(id);
+    g[to].push_back(id);
+    edges.push_back({from, to, cost});
+    return id;
+  }
+};
+// blossom / find_max_unweighted_matching
+template <typename T>
+vector<int> find_max_unweighted_matching(const undirectedgraph<T> &g) {
+  std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
+  vector<int> match(g.n, -1);   // 匹配
+  vector<int> aux(g.n, -1);     // 时间戳记
+  vector<int> label(g.n);       // "o" or "i"
+  vector<int> orig(g.n);        // 花根
+  vector<int> parent(g.n, -1);  // 父节点
+  queue<int> q;
+  int aux_time = -1;
+  auto lca = [&](int v, int u) {
+    aux_time++;
+    while (true) {
+      if (v != -1) {
+        if (aux[v] == aux_time) {  // 找到拜访过的点 也就是LCA
+          return v;
+        }
+        aux[v] = aux_time;
+        if (match[v] == -1) {
+          v = -1;
+        } else {
+          v = orig[parent[match[v]]];  // 以匹配点的父节点继续寻找
+        }
+      }
+      swap(v, u);
+    }
+  };  // lca
+  auto blossom = [&](int v, int u, int a) {
+    while (orig[v] != a) {
+      parent[v] = u;
+      u = match[v];
+      if (label[u] == 1) {  // 初始点设为"o" 找增广路
+        label[u] = 0;
+        q.push(u);
+      }
+      orig[v] = orig[u] = a;  // 缩花
+      v = parent[u];
+    }
+  };  // blossom
+  auto augment = [&](int v) {
+    while (v != -1) {
+      int pv = parent[v];
+      int next_v = match[pv];
+      match[v] = pv;
+      match[pv] = v;
+      v = next_v;
+    }
+  };  // augment
+  auto bfs = [&](int root) {
+    fill(label.begin(), label.end(), -1);
+    iota(orig.begin(), orig.end(), 0);
+    while (!q.empty()) {
+      q.pop();
+    }
+    q.push(root);
+    // 初始点设为 "o", 这里以"0"代替"o", "1"代替"i"
+    label[root] = 0;
+    while (!q.empty()) {
+      int v = q.front();
+      q.pop();
+      for (int id : g.g[v]) {
+        auto &e = g.edges[id];
+        int u = e.from ^ e.to ^ v;
+        if (label[u] == -1) {  // 找到未拜访点
+          label[u] = 1;        // 标记 "i"
+          parent[u] = v;
+          if (match[u] == -1) {  // 找到未匹配点
+            augment(u);          // 寻找增广路径
+            return true;
+          }
+          // 找到已匹配点 将与她匹配的点丢入queue 延伸交错树
+          label[match[u]] = 0;
+          q.push(match[u]);
+          continue;
+        } else if (label[u] == 0 && orig[v] != orig[u]) {
+          // 找到已拜访点 且标记同为"o" 代表找到"花"
+          int a = lca(orig[v], orig[u]);
+          // 找LCA 然后缩花
+          blossom(u, v, a);
+          blossom(v, u, a);
+        }
+      }
+    }
+    return false;
+  };  // bfs
+  auto greedy = [&]() {
+    vector<int> order(g.n);
+    // 随机打乱 order
+    iota(order.begin(), order.end(), 0);
+    shuffle(order.begin(), order.end(), rng);
+    // 将可以匹配的点匹配
+    for (int i : order) {
+      if (match[i] == -1) {
+        for (auto id : g.g[i]) {
+          auto &e = g.edges[id];
+          int to = e.from ^ e.to ^ i;
+          if (match[to] == -1) {
+            match[i] = to;
+            match[to] = i;
+            break;
+          }
+        }
+      }
+    }
+  };  // greedy
+  // 一开始先随机匹配
+  greedy();
+  // 对未匹配点找增广路
+  for (int i = 0; i < g.n; i++) {
+    if (match[i] == -1) {
+      bfs(i);
+    }
+  }
+  return match;
+}
+</code>
+</hidden>
+===== 习题 =====
+> [[https://uoj.ac/problem/79|UOJ #79. 一般图最大匹配]]
+<hidden>
+<code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+// graph
+template <typename T>
+class graph {
+ public:
+  struct edge {
+    int from;
+    int to;
+    T cost;
+  };
+  vector<edge> edges;
+  vector<vector<int> > g;
+  int n;
+  graph(int _n) : n(_n) { g.resize(n); }
+  virtual int add(int from, int to, T cost) = 0;
+};
+// undirectedgraph
+template <typename T>
+class undirectedgraph : public graph<T> {
+ public:
+  using graph<T>::edges;
+  using graph<T>::g;
+  using graph<T>::n;
+  undirectedgraph(int _n) : graph<T>(_n) {}
+  int add(int from, int to, T cost = 1) {
+    assert(0 <= from && from < n && 0 <= to && to < n);
+    int id = (int)edges.size();
+    g[from].push_back(id);
+    g[to].push_back(id);
+    edges.push_back({from, to, cost});
+    return id;
+  }
+};
+// blossom / find_max_unweighted_matching
+template <typename T>
+vector<int> find_max_unweighted_matching(const undirectedgraph<T> &g) {
+  std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
+  vector<int> match(g.n, -1);   // 匹配
+  vector<int> aux(g.n, -1);     // 时间戳记
+  vector<int> label(g.n);       // "o" or "i"
+  vector<int> orig(g.n);        // 花根
+  vector<int> parent(g.n, -1);  // 父节点
+  queue<int> q;
+  int aux_time = -1;
+  auto lca = [&](int v, int u) {
+    aux_time++;
+    while (true) {
+      if (v != -1) {
+        if (aux[v] == aux_time) {  // 找到拜访过的点 也就是LCA
+          return v;
+        }
+        aux[v] = aux_time;
+        if (match[v] == -1) {
+          v = -1;
+        } else {
+          v = orig[parent[match[v]]];  // 以匹配点的父节点继续寻找
+        }
+      }
+      swap(v, u);
+    }
+  };  // lca
+  auto blossom = [&](int v, int u, int a) {
+    while (orig[v] != a) {
+      parent[v] = u;
+      u = match[v];
+      if (label[u] == 1) {  // 初始点设为"o" 找增广路
+        label[u] = 0;
+        q.push(u);
+      }
+      orig[v] = orig[u] = a;  // 缩花
+      v = parent[u];
+    }
+  };  // blossom
+  auto augment = [&](int v) {
+    while (v != -1) {
+      int pv = parent[v];
+      int next_v = match[pv];
+      match[v] = pv;
+      match[pv] = v;
+      v = next_v;
+    }
+  };  // augment
+  auto bfs = [&](int root) {
+    fill(label.begin(), label.end(), -1);
+    iota(orig.begin(), orig.end(), 0);
+    while (!q.empty()) {
+      q.pop();
+    }
+    q.push(root);
+    // 初始点设为 "o", 这里以"0"代替"o", "1"代替"i"
+    label[root] = 0;
+    while (!q.empty()) {
+      int v = q.front();
+      q.pop();
+      for (int id : g.g[v]) {
+        auto &e = g.edges[id];
+        int u = e.from ^ e.to ^ v;
+        if (label[u] == -1) {  // 找到未拜访点
+          label[u] = 1;        // 标记 "i"
+          parent[u] = v;
+          if (match[u] == -1) {  // 找到未匹配点
+            augment(u);          // 寻找增广路径
+            return true;
+          }
+          // 找到已匹配点 将与她匹配的点丢入queue 延伸交错树
+          label[match[u]] = 0;
+          q.push(match[u]);
+          continue;
+        } else if (label[u] == 0 &&
+                   orig[v] !=
+                       orig[u]) {  // 找到已拜访点 且标记同为"o" 代表找到"花"
+          int a = lca(orig[v], orig[u]);
+          // 找LCA 然后缩花
+          blossom(u, v, a);
+          blossom(v, u, a);
+        }
+      }
+    }
+    return false;
+  };  // bfs
+  auto greedy = [&]() {
+    vector<int> order(g.n);
+    // 随机打乱 order
+    iota(order.begin(), order.end(), 0);
+    shuffle(order.begin(), order.end(), rng);
+    // 将可以匹配的点匹配
+    for (int i : order) {
+      if (match[i] == -1) {
+        for (auto id : g.g[i]) {
+          auto &e = g.edges[id];
+          int to = e.from ^ e.to ^ i;
+          if (match[to] == -1) {
+            match[i] = to;
+            match[to] = i;
+            break;
+          }
+        }
+      }
+    }
+  };  // greedy
+  // 一开始先随机匹配
+  greedy();
+  // 对未匹配点找增广路
+  for (int i = 0; i < g.n; i++) {
+    if (match[i] == -1) {
+      bfs(i);
+    }
+  }
+  return match;
+}
+int main() {
+  ios::sync_with_stdio(0), cin.tie(0);
+  int n, m;
+  cin >> n >> m;
+  undirectedgraph<int> g(n);
+  int u, v;
+  for (int i = 0; i < m; i++) {
+    cin >> u >> v;
+    u--;
+    v--;
+    g.add(u, v, 1);
+  }
+  auto blossom_match = find_max_unweighted_matching(g);
+  vector<int> ans;
+  int tot = 0;
+  for (int i = 0; i < blossom_match.size(); i++) {
+    ans.push_back(blossom_match[i]);
+    if (blossom_match[i] != -1) {
+      tot++;
+    }
+  }
+  cout << (tot >> 1) << "\n";
+  for (auto x : ans) {
+    cout << x + 1 << " ";
+  }
+}
+</hidden>
+</code>
+===== 参考链接 =====
+[[https://oi-wiki.org/topic/graph-matching/general-match/|OI Wiki]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具