Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
yukicoder No.119
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#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 <typename T>
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<vector<edge>> G;
vector<int> L;
vector<int> 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<int> 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment