結果

問題 No.119 旅行のツアーの問題
ユーザー eiuru
提出日時 2024-04-03 15:43:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,568 bytes
コンパイル時間 2,049 ms
コンパイル使用メモリ 210,388 KB
最終ジャッジ日時 2025-02-20 19:53:21
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; ++i)
using namespace std;
using ll = long long;
template <class C> 
struct Flow {
private:
  int n;
  vector<pair<int,int>> p;
  vector<vector<tuple<int,int,C>>> g;
public:
  Flow(int n):n(n),g(n){}
  struct E {
    int u, v; C c, f;
  };
  int add(int u, int v, C c) {
    int ui = int(g[u].size());
    int vi = int(g[v].size());
    if (u==v) ++vi;
    p.emplace_back(u,ui);
    g[u].emplace_back(v,vi,c);
    g[v].emplace_back(u,ui,0);
    return int(p.size()) - 1;
  }
  E getEdge(int i) {
    auto&[v,vi,cv] = g[p[i].first][p[i].second];
    auto&[u,ui,cu] = g[v][vi];
    return E{u, v, cu+cv, cu};
  }
  void changeEdge(int i, C c, C f) {
    auto&[v,vi,cv] = g[p[i].first][p[i].second];
    auto&[u,ui,cu] = g[v][vi];
    cv = c - f;
    cu = f;
  }

  C flow(int s, int t, C flow = numeric_limits<C>::max()) {
    vector<int> depth(n);
    auto bfs = [&]{
      fill(depth.begin(), depth.end(), -1);
      depth[s] = 0;
      queue<int> q;
      q.push(s);
      while(q.size()){
        int u = q.front(); q.pop();
        for (auto [v,vi,c]:g[u]) {
          if (c==0 || depth[v]>=0) continue;
          depth[v] = depth[u]+1;
          if(v==t) return true;
          q.push(v);
        }
      }
      return false;
    };
    function<C(int,C)> dfs = [&](int v, C up){
      if(v==s) return up;
      C res = 0;
      for(auto&[u,ui,cu]:g[v]){
        auto&[_,vi,cv] = g[u][ui];
        if (depth[v]<=depth[u]||cv==0) continue;
        C f = dfs(u, min(up-res, cv));
        if (f<=0) continue;
        cu += f;
        cv -= f;
        res += f;
        if (res == up) return res;
      }
      depth[v] = n;
      return res;
    };

    C res = 0;
    while(flow && bfs()){
      C f = dfs(t,flow);
      flow -= f;
      res += f;
    }
    return res;
  }

  vector<bool> cut(int s) {
    vector<bool> res(n);
    queue<int> q;
    q.push(s);
    while (q.size()) {
      int u = q.front(); q.pop();
      res[u] = true;
      for(auto&[v,vi,c]:g[u]){
        if (c&&!res[v]) {
          res[v] = true;
          q.push(v);
        }
      }
    }
    return res;
  }
};

int n,m,b,c,d,e;
int f(int i,int j){ return i*2+j; }
int main() {
  cin >> n;
  int s = n*2, t = s+1;
  Flow<ll> v(t+1);
  ll ans = 0;
  rep(i,n){
    cin >> b >> c;
    ans += b+c;
    v.add(s,f(i,0),b);
    v.add(f(i,0),f(i,1),b+c);
    v.add(f(i,1),t,c);
    v.add(f(i,1),f(i,0),1e9);
  }
  cin >> m;
  rep(_,m){
    cin >> d >> e;
    v.add(f(d,1),f(e,0),1e9);
  }
  ans -= v.flow(s,t);
  cout << ans << endl;
}
0