test/yosupo/graph/matching_on_bipartite_garph.test.cpp

• View this file on GitHub
• Last update: 2025-05-22 18:45:59+09:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

• 最大流 (lib/flow/max_flow.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/bipartitematching
#include <iostream>
#include <utility>
#include <vector>
#include "flow/max_flow.hpp"

int main(void) {
    int l, r, m;
    std::cin >> l >> r >> m;
    std::vector<std::pair<int, int>> p(m);
    for (auto &[a, b] : p) std::cin >> a >> b;
    mf_graph<int> mf(l + r + 2);
    int s = l + r, g = s + 1;
    for (auto &&x : p) mf.add_edge(x.first, l + x.second, 1);
    for (int i = 0; i < l; ++i) mf.add_edge(s, i, 1);
    for (int i = 0; i < r; ++i) mf.add_edge(l + i, g, 1);
    mf.flow(s, g);
    std::vector<int> ans;
    for (int i = 0; i < m; ++i) {
        if (mf.get_edge(i).flow == 1) ans.emplace_back(i);
    }
    std::cout << ans.size() << '\n';
    for (auto &&x : ans) std::cout << p[x].first << ' ' << p[x].second << '\n';

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: flow/max_flow.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	augmented_cycle_00	AC	1410 ms	31 MB
g++	augmented_cycle_01	AC	903 ms	32 MB
g++	augmented_cycle_02	AC	1366 ms	32 MB
g++	cycle_00	AC	594 ms	41 MB
g++	cycle_01	AC	667 ms	45 MB
g++	example_00	AC	2 ms	3 MB
g++	issue1068_00	AC	2 ms	4 MB
g++	issue1068_large_00	AC	116 ms	27 MB
g++	issue1068_large_01	AC	115 ms	26 MB
g++	issue1068_large_02	AC	144 ms	26 MB
g++	issue1068_large_03	AC	124 ms	34 MB
g++	issue1068_large_04	AC	118 ms	26 MB
g++	issue1068_large_05	AC	152 ms	35 MB
g++	issue1124_00	AC	141 ms	22 MB
g++	issue1124_01	AC	96 ms	21 MB
g++	issue1124_02	AC	93 ms	22 MB
g++	kuhn_killer_00	AC	139 ms	31 MB
g++	line_00	AC	193 ms	60 MB
g++	line_01	AC	199 ms	59 MB
g++	line_random_00	AC	717 ms	58 MB
g++	line_random_01	AC	610 ms	40 MB
g++	many_paths_00	AC	704 ms	32 MB
g++	many_paths_01	AC	634 ms	32 MB
g++	many_paths_02	AC	746 ms	32 MB
g++	many_smalls_00	AC	173 ms	24 MB
g++	many_smalls_01	AC	161 ms	23 MB
g++	max_random_00	AC	237 ms	30 MB
g++	max_random_01	AC	229 ms	30 MB
g++	max_random_02	AC	218 ms	30 MB
g++	random_00	AC	23 ms	12 MB
g++	random_01	AC	92 ms	19 MB
g++	random_02	AC	89 ms	17 MB
g++	random_03	AC	88 ms	15 MB
g++	random_04	AC	34 ms	14 MB
g++	random_05	AC	40 ms	11 MB
g++	random_06	AC	174 ms	22 MB
g++	random_07	AC	34 ms	14 MB
g++	random_08	AC	96 ms	18 MB
g++	random_09	AC	96 ms	18 MB
g++	unique_matching_00	AC	1277 ms	38 MB
g++	unique_matching_01	AC	1462 ms	33 MB
g++	unique_matching_02	AC	1135 ms	32 MB
g++	unique_matching_03	AC	572 ms	30 MB
g++	unique_matching_04	AC	440 ms	31 MB

Back to top page