Submit Info #2678

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

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.55 MiB
line_00 AC 60 ms 8.25 MiB
line_01 AC 67 ms 8.25 MiB
many_smalls_00 AC 58 ms 5.18 MiB
many_smalls_01 AC 57 ms 5.16 MiB
max_random_00 WA 70 ms 7.64 MiB
max_random_01 AC 70 ms 7.75 MiB
max_random_02 AC 73 ms 7.64 MiB
random_00 AC 9 ms 1.75 MiB
random_01 AC 47 ms 5.13 MiB
random_02 AC 34 ms 4.25 MiB
random_03 AC 77 ms 3.75 MiB
random_04 AC 13 ms 1.99 MiB
random_05 AC 21 ms 3.37 MiB
random_06 AC 70 ms 5.25 MiB
random_07 AC 16 ms 4.50 MiB
random_08 AC 31 ms 2.21 MiB
random_09 AC 47 ms 4.93 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() { int L,R,M; scanf("%d %d %d", &L, &R, &M); BiMatching bm(L,R); rep (i,M) { int a,b; scanf("%d %d",&a,&b); bm.add_edge(a,b); } printf("%d\n", bm.run()); rep (i,L) if (bm.p[i] >= 0) printf("%d %d\n", i, bm.p[i]); }