結果

問題 No.119 旅行のツアーの問題
ユーザー pionepione
提出日時 2021-04-11 12:58:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,907 bytes
コンパイル時間 2,421 ms
コンパイル使用メモリ 215,856 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 08:15:49
合計ジャッジ時間 3,234 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define irreps(i, m, n) for (int i = ((int)(n)-1); i > (int)(m); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) (int)(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;
using ld = long double;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

const ll INF = 1e9+10;
// const ll MOD = 1e9+7;
const ll MOD = 998244353;
const ll LINF = 1e18;

/// @see[https://pione.hatenablog.com/entry/2021/02/27/061552]
template <class T>
class Dinic {
private:
  const int INF = 1e9;
  vector<int> level, itr;

  struct Edge {
    int to, rev; T cap;
    Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
  };

  vector<vector<Edge>> G;

  Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }

  void bfs(int s) {
    level.assign(G.size(), -1);
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      auto v = q.front();
      q.pop();
      for (auto &e : G[v]) {
        if (level[e.to] < 0 and e.cap > 0) {
          level[e.to] = level[v] + 1;
          q.push(e.to);
        }
      }
    }
  }

  T dfs(int v, int t, T flow) {
    if (v == t) return flow;
    for (int &i = itr[v]; i < G[v].size(); i++) {
      auto &edge = G[v][i];
      if (level[v] < level[edge.to] and edge.cap > 0) {
        auto f = dfs(edge.to, t, min(flow, edge.cap));
        if (f > 0) {
          edge.cap -= f;
          get_rev(edge).cap += f;
          return f;
        }
      }
    }
    return 0;
  }

public:
  Dinic(int n) { G.resize(n); }

  void add_edge(int from, int to, T cap) {
    G[from].push_back(Edge(to, (int)G[to].size(), cap));
    G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
  }

  T get_max_flow(int s, int t) {
    int n = G.size();
    T res = 0;
    while (true) {
      itr.assign(n, 0);
      bfs(s);
      if (level[t] < 0) break;
      while (true) {
        T flow = dfs(s, t, INF);
        if (flow > 0) res += flow;
        else break;
      }
    }
    return res;
  }
};

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int n; cin>>n;
  auto flow=Dinic<ll>(2*n+2);
  ll ans=0;
  rep(i,n){
    ll b,c; cin>>b>>c;
    ans+=b+c; // b[i]+c[i]が取れるという仮定から、取れない場合のグラフの最小カットを引く
    flow.add_edge(2*n,i,b); // iのツアーに行くのを諦める
    flow.add_edge(i+n,2*n+1,c); // iにただ行くのを諦める
  }
  
  int m; cin>>m;
  rep(i,m){
    int d,e; cin>>d>>e;
    flow.add_edge(d,e+n,INF);
  }
  
  // iへツアー&ただ行く、の両方を諦めるパターン
  rep(i,n){
    flow.add_edge(i,i+n,INF);
  }
  
  ans-=flow.get_max_flow(2*n,2*n+1);
  cout<<ans<<endl;
}
0