Instantly share code, notes, and snippets.

# ctylim/yukicoder119.cpp Created Nov 30, 2015

What would you like to do?
yukicoder No.119
 #include #include #include #include #include #include #include #include #include #include #include #include #include #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) #define var auto #define mod 1000000007 #define inf 2147483647 #define nil -1 typedef long long ll; using namespace std; inline int input(){ int a; cin >> a; return a; } template inline void output(T a, int p) { if(p){ cout << fixed << setprecision(p) << a << "\n"; } else{ cout << a << "\n"; } } // goal, capacity, index of reverse edge struct edge { int to, cap, rev; }; // O(EV^2) class Dinic{ public: int V; vector> G; vector L; vector I; Dinic(int v){ G.resize(v), L.resize(v), I.resize(v); V = v; } // add edge void add(int from, int to, int cap){ G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size() - 1}); } // label dist from s void bfs(int s){ L.assign(V, -1); queue q; L[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); rep(i, G[v].size()){ edge &e = G[v][i]; if (e.cap > 0 && L[e.to] < 0) { L[e.to] = L[v] + 1; q.push(e.to); } } } } // search positive path int dfs(int v, int t, int f){ if (v == t) return f; for (int &i = I[v]; i < G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && L[v] < L[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } // calc max flow int max_flow(int s, int t){ int flow = 0; for (;;) { bfs(s); if (L[t] < 0) return flow; I.assign(V, 0); int f; while ((f = dfs(s, t, inf)) > 0) { flow += f; } } } }; // end of template int main() { cin.tie(0); // source code int N = input(); Dinic D(2 * N + 2); int sum = 0; rep(i, N){ int B, C; cin >> B >> C; D.add(0, i + 1, max(B, C) - B); D.add(i + 1, i + N + 1, max(B, C)); D.add(i + N + 1, 2 * N + 1, max(B, C) - C); sum += max(B, C); } int M = input(); rep(i, M){ int X, Y; cin >> X >> Y; D.add(Y + N + 1, X + 1, inf); } cout << sum - D.max_flow(0, 2 * N + 1); return 0; }