#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() enum EdgeType { Directed, Undirected }; template struct revCap { static T value(T cap) { (void)cap; return 0; } }; template struct revCap { static T value(T cap) { return cap; } }; template class MF { public: struct Edge { Edge(int t, T c, int r) : to(t), cap(c), rev(r) {} int to; T cap; int rev; }; std::vector> edges_; std::vector iter_; std::vector level_; MF(int v) : edges_(v) {} MF() {} ~MF() {} void init(int v) { edges_.resize(v); } void bfs(int from) { std::fill(level_.begin(), level_.end(), -1); std::queue que; level_[from] = 0; que.push(from); while (!que.empty()) { int v = que.front(); que.pop(); REP(i, edges_[v].size()) { Edge &e = edges_[v][i]; if (e.cap > 0 && level_[e.to] < 0) { level_[e.to] = level_[v]+1; que.push(e.to); } } } return; } T dfs(int v, int to, T f) { if (v == to) return f; for (int &i = iter_[v]; i < edges_[v].size(); ++i) { Edge &e = edges_[v][i]; if (e.cap > 0 && level_[v] < level_[e.to]) { int d = dfs(e.to, to, std::min(f, e.cap)); if (d > 0) { e.cap -= d; edges_[e.to][e.rev].cap += d; return d; } } } return 0; } T max_flow(int from, int to, T inf = std::numeric_limits::max()) { int v = edges_.size(); iter_.resize(v, 0); level_.resize(v, -1); int flow = 0; while (true) { bfs(from); if (level_[to] < 0) return flow; std::fill(iter_.begin(), iter_.end(), 0); int f; while ((f = dfs(from, to, inf))) flow += f; } return -1; } void add(int a, int b, T cap) { edges_[a].emplace_back(b,cap,edges_[b].size()); edges_[b].emplace_back(a,revCap::value(cap),edges_[a].size()-1); } }; using namespace std; class TravelTourProblem { public: // 全ての国に訪れるケースを考えると各国に対してツアーに参加するかどうかの二値分類問題になる。 // よってその場合は最小カットで解ける。(全流量からカットした分 B or C を取り除く。) // // 問題は国に訪れないケースも考える必要がある場合。 // この場合は両方の総和 B+C を取り除くと考える。 // void solve(void) { int N,M; cin>>N; int V = 2*N+2; int src = V-2; // ツアー未参加側 int sink = src+1; // ツアー参加側 int total = 0; MF mf(V); const auto inf = (1<<30); REP(i,N) { int B,C; cin>>B>>C; total += (B+C); mf.add(src, i, C); mf.add(i+N, sink, B); mf.add(i,i+N,B+C); // 国に訪れないケースはここを切断すればよい。 } cin>>M; REP(i,M) { int D,E; cin>>D>>E; // // +-> E1->E2 -/-+ // | v | // src-+ +---+ +-> sink // | v | // +-> D1->D2 ---+ // // E 番目のツアー参加への辺を切断しても D->sink が残っているなら // flow cut できないようにする。 // mf.add(E+N,D,inf); } total -= mf.max_flow(src,sink,inf); cout<solve(); delete obj; return 0; } #endif