| 2 | int dist[MAXN+1], q[MAXN+1]; |
| 3 | #define dist(v) dist[v == -1 ? MAXN : v] |
| 4 | struct bipartite_graph { |
| 5 | int N, M, *L, *R; vi *adj; |
| 6 | bipartite_graph(int _N, int _M) : N(_N), M(_M), |
| 7 | L(new int[N]), R(new int[M]), adj(new vi[N]) {} |
| 8 | ~bipartite_graph() { delete[] adj; delete[] L; delete[] R; } |
| 9 | bool bfs() { |
| 10 | int l = 0, r = 0; |
| 11 | rep(v,0,N) if(L[v] == -1) dist(v) = 0, q[r++] = v; |
| 12 | else dist(v) = INF; |
| 13 | dist(-1) = INF; |
| 14 | while(l < r) { |
| 15 | int v = q[l++]; |
| 16 | if(dist(v) < dist(-1)) { |
| 17 | iter(u, adj[v]) if(dist(R[*u]) == INF) |
| 18 | dist(R[*u]) = dist(v) + 1, q[r++] = R[*u]; } } |
| 19 | return dist(-1) != INF; } |
| 20 | bool dfs(int v) { |
| 21 | if(v != -1) { |
| 22 | iter(u, adj[v]) |
| 23 | if(dist(R[*u]) == dist(v) + 1) |
| 24 | if(dfs(R[*u])) { |
| 25 | R[*u] = v, L[v] = *u; |
| 26 | return true; } |
| 27 | dist(v) = INF; |
| 28 | return false; } |
| 29 | return true; } |
| 30 | void add_edge(int i, int j) { adj[i].push_back(j); } |
| 31 | int maximum_matching() { |
| 32 | int matching = 0; |
| 33 | memset(L, -1, sizeof(int) * N); |
| 34 | memset(R, -1, sizeof(int) * M); |
| 35 | while(bfs()) rep(i,0,N) |
| 36 | matching += L[i] == -1 && dfs(i); |
| 37 | return matching; } }; |
| 38 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected