This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 二部マッチング (最大流を使って解く) // ・普通に辺を張る他に、自分で別に頂点を 2 つ用意する template <typename T> struct Edge { int to; T cap, cost; int rev; Edge(int t, T c, int r) : to(t), cap(c), rev(r) {} Edge(int t, T ca, T co, int r) : to(t), cap(ca), cost(co), rev(r) {} }; template <typename T> using Graph = vector< vector< Edge<T> > >; struct BipartiteMatching { int S, T, E, a, b; vector< vector< Edge<int> > > G; vector<int> used; BipartiteMatching(int x, int y, int z) : S(x), T(y), E(z) { G.resize(S+T+2); used.resize(S+T+2); a = S + T, b = a + 1; for(int i=0; i<S; i++) add_edge(a , i, 1); for(int i=0; i<T; i++) add_edge(i+S, b, 1); } void add_edge(int from, int to, int cap) { G[from].push_back(Edge<int>(to , cap, G[to ].size() )); G[to ].push_back(Edge<int>(from, 0 , G[from].size() - 1)); } void readGraph() { for(int i=0; i<E; i++) { int x, y; cin >> x >> y; // x--; y--; add_edge(x, y+S, 1); } } int dfs(int v, int t, int f) { if(v == t) return f; used[v] = true; for(size_t i=0; i<G[v].size(); i++) { Edge<int> &e = G[v][i]; if(!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int solve() { int flow = 0; while(1) { fill(used.begin(), used.end(), 0); int f = dfs(a, b, INF); if(f == 0) return flow; flow += f; } } }; /* signed main() { int x, y, e; cin >> x >> y >> e; BipartiteMatching B(x, y, e); B.readGraph(); cout << B.solve() << endl; return 0; } */
#line 1 "graph/graph_017_bipartite.cpp" // 二部マッチング (最大流を使って解く) // ・普通に辺を張る他に、自分で別に頂点を 2 つ用意する template <typename T> struct Edge { int to; T cap, cost; int rev; Edge(int t, T c, int r) : to(t), cap(c), rev(r) {} Edge(int t, T ca, T co, int r) : to(t), cap(ca), cost(co), rev(r) {} }; template <typename T> using Graph = vector< vector< Edge<T> > >; struct BipartiteMatching { int S, T, E, a, b; vector< vector< Edge<int> > > G; vector<int> used; BipartiteMatching(int x, int y, int z) : S(x), T(y), E(z) { G.resize(S+T+2); used.resize(S+T+2); a = S + T, b = a + 1; for(int i=0; i<S; i++) add_edge(a , i, 1); for(int i=0; i<T; i++) add_edge(i+S, b, 1); } void add_edge(int from, int to, int cap) { G[from].push_back(Edge<int>(to , cap, G[to ].size() )); G[to ].push_back(Edge<int>(from, 0 , G[from].size() - 1)); } void readGraph() { for(int i=0; i<E; i++) { int x, y; cin >> x >> y; // x--; y--; add_edge(x, y+S, 1); } } int dfs(int v, int t, int f) { if(v == t) return f; used[v] = true; for(size_t i=0; i<G[v].size(); i++) { Edge<int> &e = G[v][i]; if(!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int solve() { int flow = 0; while(1) { fill(used.begin(), used.end(), 0); int f = dfs(a, b, INF); if(f == 0) return flow; flow += f; } } }; /* signed main() { int x, y, e; cin >> x >> y >> e; BipartiteMatching B(x, y, e); B.readGraph(); cout << B.solve() << endl; return 0; } */