test/yosupo-judge/bipartitematching/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching
• Link: View error logs on GitHub Actions

Depends on

• Hopcroft-Karp algorithm (Mylib/Graph/Matching/hopcroft_karp.cpp)
• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuples (Mylib/IO/input_tuples.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"

#include <iostream>
#include "Mylib/Graph/Matching/hopcroft_karp.cpp"
#include "Mylib/IO/input_tuples.cpp"

namespace hl = haar_lib;

int main() {
  int L, R, M;
  std::cin >> L >> R >> M;
  hl::hopcroft_karp hk(L, R);

  for (auto [a, b] : hl::input_tuples<int, int>(M)) {
    hk.add_edge(a, b);
  }

  hk.match();

  auto ans = hk.get_matching();

  std::cout << ans.size() << "\n";
  for (auto& [i, j] : ans) {
    std::cout << i << " " << j << "\n";
  }

  return 0;
}

#line 1 "test/yosupo-judge/bipartitematching/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"

#include <iostream>
#line 2 "Mylib/Graph/Matching/hopcroft_karp.cpp"
#include <cassert>
#include <queue>
#include <utility>
#include <vector>

namespace haar_lib {
  class hopcroft_karp {
    struct edge {
      int from, to;
      int rev;
      bool used;
    };

    int L_, R_, N_;
    std::vector<std::vector<edge>> g_;
    std::vector<int> dist_;

    bool bfs() {
      dist_.assign(N_, -1);
      std::queue<int> q;

      q.push(0);
      dist_[0] = 0;

      while (not q.empty()) {
        int i = q.front();
        q.pop();

        for (auto &e : g_[i]) {
          if (not e.used and dist_[e.to] == -1) {
            dist_[e.to] = dist_[i] + 1;
            q.push(e.to);
          }
        }
      }

      return dist_[N_ - 1] != -1;
    }

    bool dfs(int cur) {
      if (cur == N_ - 1) return true;

      for (auto &e : g_[cur]) {
        if (not e.used and dist_[cur] + 1 == dist_[e.to]) {
          if (dfs(e.to)) {
            e.used = true;
            if (e.rev >= 0) g_[e.to][e.rev].used = false;
            return true;
          }
        }
      }

      return false;
    }

  public:
    hopcroft_karp() {}
    hopcroft_karp(int L, int R) : L_(L), R_(R), N_(L + R + 2), g_(N_), dist_(N_) {
      for (int i = 0; i < L_; ++i) {
        g_[0].push_back((edge){0, i + 1, -1, false});
      }

      for (int i = 0; i < R_; ++i) {
        g_[i + L_ + 1].push_back((edge){i + L_ + 1, N_ - 1, -1, false});
      }
    }

    void add_edge(int i, int j) {
      assert(0 <= i and i < L_);
      assert(0 <= j and j < R_);

      const int x = i + 1;
      const int y = j + L_ + 1;

      g_[x].push_back((edge){x, y, (int) g_[y].size(), false});
      g_[y].push_back((edge){y, x, (int) g_[x].size() - 1, true});
    }

    int match() {
      int ret = 0;

      while (bfs()) {
        int flow = 0;
        for (int i = 0; i < L_; ++i) {
          auto &e = g_[0][i];
          if (not e.used and dfs(e.to)) {
            e.used = true;
            ++flow;
          }
        }
        if (flow == 0) break;
        ret += flow;
      }

      return ret;
    }

    auto get_matching() {
      std::vector<std::pair<int, int>> ret;
      for (int i = 0; i < L_; ++i) {
        for (auto &e : g_[i + 1]) {
          if (e.used) ret.emplace_back(i, e.to - L_ - 1);
        }
      }
      return ret;
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuples {
    struct iter {
      using value_type = std::tuple<Args...>;
      value_type value;
      bool fetched = false;
      int N, c = 0;

      value_type operator*() {
        if (not fetched) {
          std::cin >> value;
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuples(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples(int N) {
    return InputTuples<Args...>(N);
  }
}  // namespace haar_lib
#line 6 "test/yosupo-judge/bipartitematching/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int L, R, M;
  std::cin >> L >> R >> M;
  hl::hopcroft_karp hk(L, R);

  for (auto [a, b] : hl::input_tuples<int, int>(M)) {
    hk.add_edge(a, b);
  }

  hk.match();

  auto ans = hk.get_matching();

  std::cout << ans.size() << "\n";
  for (auto& [i, j] : ans) {
    std::cout << i << " " << j << "\n";
  }

  return 0;
}

Back to top page