Submit Info #2680

Problem Lang User Status Time Memory
Matching on Bipartite Graph cpp (anonymous) WA 78 ms 8.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.60 MiB
line_00 AC 60 ms 8.30 MiB
line_01 AC 60 ms 8.25 MiB
many_smalls_00 AC 58 ms 5.25 MiB
many_smalls_01 AC 58 ms 5.29 MiB
max_random_00 WA 72 ms 7.68 MiB
max_random_01 AC 74 ms 7.72 MiB
max_random_02 AC 73 ms 7.67 MiB
random_00 AC 10 ms 1.84 MiB
random_01 AC 49 ms 5.13 MiB
random_02 AC 34 ms 4.30 MiB
random_03 AC 78 ms 3.75 MiB
random_04 AC 12 ms 1.93 MiB
random_05 AC 20 ms 3.49 MiB
random_06 AC 71 ms 5.24 MiB
random_07 AC 17 ms 4.50 MiB
random_08 AC 34 ms 2.16 MiB
random_09 AC 46 ms 5.04 MiB

#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < (int)(n); i++) struct BiMatching { int val = 0; vector<int> used,p,q; vector<vector<int> > g; BiMatching(int L, int R) : used(L,0), p(L,-1), q(R,-1), g(L) {} void add_edge(int x, int y) { g[x].push_back(y); } bool dfs(int x) { if (used[x] == val) return false; used[x] = val; for (int y : g[x]) { if (q[y] >= 0 && !dfs(q[y])) continue; p[x] = y, q[y] = x; return true; } return false; } int run() { int match = 0, u = 1; while (u) { u = 0, val = ~val; rep (i,p.size()) if (!~p[i] && dfs(i)) u = 1, ++match; } return match; } }; int32_t main() { cin.tie(nullptr); ios::sync_with_stdio(false); int L,R,M; cin >> L >> R >> M; BiMatching bm(L,R); rep (i,M) { int a,b; cin >> a >> b; bm.add_edge(a,b); } cout << bm.run() << "\n"; rep (i,L) if (bm.p[i] >= 0) cout << i << " " << bm.p[i] << "\n"; }