グラフ/フロー/マッチング/二部グラフの最大マッチング
(test/graph/flow/matching/bipartite_matching.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A

Depends on

• 二部グラフの最大マッチング (include/emthrm/graph/flow/matching/bipartite_matching.hpp)

Code

/*
 * @title グラフ/フロー/マッチング/二部グラフの最大マッチング
 *
 * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A
 */

#include <iostream>

#include "emthrm/graph/flow/matching/bipartite_matching.hpp"

int main() {
  int x, y, e;
  std::cin >> x >> y >> e;
  emthrm::BipartiteMatching bipartite_matching(x + y);
  while (e--) {
    int x_i, y_i;
    std::cin >> x_i >> y_i;
    bipartite_matching.add_edge(x_i, y_i + x);
  }
  std::cout << bipartite_matching.solve() << '\n';
  return 0;
}

#line 1 "test/graph/flow/matching/bipartite_matching.test.cpp"
/*
 * @title グラフ/フロー/マッチング/二部グラフの最大マッチング
 *
 * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A
 */

#include <iostream>

#line 1 "include/emthrm/graph/flow/matching/bipartite_matching.hpp"



#include <vector>

namespace emthrm {

struct BipartiteMatching {
  std::vector<int> match;

  explicit BipartiteMatching(const int n)
      : match(n, -1), n(n), t(0), is_alive(n, true), is_used(n, 0), graph(n) {}

  void add_edge(const int u, const int v) {
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
  }

  int solve() {
    int res = 0;
    for (int i = 0; i < n; ++i) {
      if (is_alive[i] && match[i] == -1) {
        ++t;
        res += dfs(i);
      }
    }
    return res;
  }

  void fix(const int ver) {
    is_alive[ver] = false;
    if (match[ver] != -1) is_alive[match[ver]] = false;
  }

  int activate(const int ver) {
    if (is_alive[ver]) return 0;
    is_alive[ver] = true;
    ++t;
    return dfs(ver) ? 1 : 0;
  }

  int deactivate(const int ver) {
    if (!is_alive[ver]) return 0;
    is_alive[ver] = false;
    const int m = match[ver];
    if (m == -1) return 0;
    match[ver] = match[m] = -1;
    ++t;
    return dfs(m) ? 0 : -1;
  }

 private:
  const int n;
  int t;
  std::vector<bool> is_alive;
  std::vector<int> is_used;
  std::vector<std::vector<int>> graph;

  bool dfs(const int ver) {
    is_used[ver] = t;
    for (const int dst : graph[ver]) {
      if (!is_alive[dst]) continue;
      const int m = match[dst];
      if (m == -1 || (is_used[m] < t && dfs(m))) {
        match[ver] = dst;
        match[dst] = ver;
        return true;
      }
    }
    return false;
  }
};

}  // namespace emthrm


#line 10 "test/graph/flow/matching/bipartite_matching.test.cpp"

int main() {
  int x, y, e;
  std::cin >> x >> y >> e;
  emthrm::BipartiteMatching bipartite_matching(x + y);
  while (e--) {
    int x_i, y_i;
    std::cin >> x_i >> y_i;
    bipartite_matching.add_edge(x_i, y_i + x);
  }
  std::cout << bipartite_matching.solve() << '\n';
  return 0;
}

Back to top page