結果

問題 No.119 旅行のツアーの問題
コンテスト
ユーザー hashiryo
提出日時 2021-12-16 16:38:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 7,870 bytes
コンパイル時間 2,782 ms
コンパイル使用メモリ 223,464 KB
最終ジャッジ日時 2025-01-26 23:34:50
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << '\n'
#define debugMatrix(x, h, w)                                         \
  cerr << __LINE__ << ": " << #x << " =\n";                          \
  for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) {      \
    cerr << ((hoge ? " {" : "{{"));                                  \
    for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga))      \
      cerr << ((fuga ? ", " : "")) << x[hoge][fuga];                 \
    cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \
  }
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

template <typename FlowAlgo>
struct MaxFlow : public FlowAlgo {
  using FlowAlgo::FlowAlgo;
  using Edge = typename FlowAlgo::Edge;
  using flow_t = decltype(Edge::cap);
  int add_vertex() { return this->adj.resize(++this->n), this->n - 1; }
  std::vector<int> add_vertices(const std::size_t size) {
    std::vector<int> ret(size);
    std::iota(ret.begin(), ret.end(), this->n);
    return this->adj.resize(this->n += size), ret;
  }
  struct EdgePtr {
    friend class MaxFlow;
    MaxFlow *instance;
    int v, e;
    bool bidir;
    Edge &edge() { return instance->adj[v][e]; }
    Edge &rev() {
      Edge &e = edge();
      return instance->adj[e.dst][e.rev];
    }
    EdgePtr(MaxFlow *instance, int v, int e, bool d)
        : instance(instance), v(v), e(e), bidir(d) {}

   public:
    EdgePtr() = default;
    int src() { return v; }
    int dst() { return edge().dst; }
    bool is_direct() const { return !bidir; }
    flow_t flow() { return cap() - edge().cap; }
    flow_t cap() { return (edge().cap + rev().cap) / (1 + bidir); }
    flow_t change_cap(flow_t new_cap, int s, int t) {
      assert(0 <= new_cap);
      Edge &e = edge(), &re = rev();
      flow_t diff = new_cap - cap(), extrusion = std::abs(flow()) - new_cap;
      if (extrusion <= 0) return e.cap += diff, re.cap += diff * bidir, 0;
      int sr = src(), ds = dst();
      if (flow() < 0) std::swap(sr, ds);
      if (bidir) {
        if (sr == src())
          re.cap += 2 * diff + e.cap, e.cap = 0;
        else
          e.cap += 2 * diff + re.cap, re.cap = 0;
      } else
        re.cap += diff;
      extrusion -= instance->maxflow(sr, ds, extrusion);
      if (ds != t) instance->maxflow(t, ds, extrusion);
      if (sr != s) instance->maxflow(sr, s, extrusion);
      return extrusion;
    }
  };
  EdgePtr add_edge(int src, int dst, flow_t cap, bool bidir = false) {
    assert(0 <= src && src < this->n);
    assert(0 <= dst && dst < this->n);
    assert(0 <= cap);
    int e = this->adj[src].size();
    int re = src == dst ? e + 1 : this->adj[dst].size();
    this->adj[src].push_back(Edge{dst, re, cap});
    this->adj[dst].push_back(Edge{src, e, cap * bidir});
    return this->m++, EdgePtr{this, src, e, bidir};
  }
  flow_t maxflow(int s, int t) {
    return maxflow(s, t, std::numeric_limits<flow_t>::max());
  }
  flow_t maxflow(int s, int t, flow_t flow_lim) {
    return this->flow(s, t, flow_lim);
  }
  std::vector<bool> mincut(int s) {
    std::vector<bool> visited(this->n);
    static std::queue<int> que;
    for (que.push(s); !que.empty();) {
      int p = que.front();
      que.pop(), visited[p] = true;
      for (const auto &e : this->adj[p])
        if (e.cap && !visited[e.dst]) visited[e.dst] = true, que.push(e.dst);
    }
    return visited;
  }
};

template <class flow_t>
struct Dinic {
  Dinic(std::size_t _n = 0) : n(_n), m(0), adj(n) {}

 protected:
  struct Edge {
    int dst, rev;
    flow_t cap;
  };
  int n, m;
  std::vector<std::vector<Edge>> adj;
  std::vector<int> level, iter;
  inline void levelize(const int &s, const int &t) {
    level.assign(n, -1), level[s] = 0;
    std::queue<int> que;
    for (que.push(s); !que.empty();) {
      int u = que.front();
      que.pop();
      for (auto &e : adj[u])
        if (e.cap > 0 && level[e.dst] < 0) {
          level[e.dst] = level[u] + 1;
          if (e.dst == t) return;
          que.push(e.dst);
        }
    }
  }
  inline flow_t dfs(int u, const int &s, flow_t cur) {
    if (u == s) return cur;
    flow_t ret = 0;
    for (int &i = iter[u]; i < adj[u].size(); i++) {
      Edge &e = adj[u][i], &re = adj[e.dst][e.rev];
      if (level[u] <= level[e.dst] || re.cap == 0) continue;
      flow_t f = dfs(e.dst, s, std::min(cur - ret, re.cap));
      if (f <= 0) continue;
      e.cap += f, re.cap -= f, ret += f;
      if (ret == cur) return ret;
    }
    return level[u] = n, ret;
  }
  flow_t flow(int s, int t, flow_t flow_lim) {
    assert(0 <= s && s < n);
    assert(0 <= t && t < n);
    assert(s != t);
    flow_t ret = 0;
    for (flow_t f; ret < flow_lim; ret += f) {
      if (levelize(s, t), level[t] == -1) break;
      iter.assign(n, 0);
      if (!(f = dfs(t, s, flow_lim - ret))) break;
    }
    return ret;
  }
};

template <typename T, typename MF, typename Th, typename Ph>
auto monge_mincut(int n, int k, Th theta, Ph phi) {
  static_assert(std::is_same_v<T, typename MF::flow_t>);
  static constexpr T INF = std::numeric_limits<T>::max();
  T ret = 0;
  MF graph;
  int s = graph.add_vertex(), t = graph.add_vertex();
  std::vector<std::vector<int>> x;
  std::vector<std::vector<T>> th(n, std::vector<T>(k));
  for (int i = 0; i < n; i++) {
    x.emplace_back(graph.add_vertices(k - 1));
    for (int l = 1; l < k - 1; l++) graph.add_edge(x[i][l], x[i][l - 1], INF);
    for (int l = 0; l < k; l++) th[i][l] = theta(i, l);
  }
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      for (int l = 0; l < k - 1; l++)
        for (int m = 0; m < k - 1; m++) {
          T cost = -phi(i, j, l + 1, m + 1) + phi(i, j, l, m + 1) +
                   phi(i, j, l + 1, m) - phi(i, j, l, m);
          assert(cost >= 0);  // monge
          if (cost > 0) graph.add_edge(x[i][l], x[j][m], cost);
        }
      for (int l = 0; l < k; l++) th[i][l] += phi(i, j, l, k - 1);
      for (int l = 0; l < k; l++) th[j][l] += phi(i, j, 0, l);
      ret -= phi(i, j, 0, k - 1);
    }
  for (int i = 0; i < n; i++) {
    ret += th[i][0];
    for (int l = 0; l < k - 1; l++) {
      T cost = th[i][l] - th[i][l + 1];
      if (cost > 0) graph.add_edge(s, x[i][l], cost), ret -= cost;
      if (cost < 0) graph.add_edge(x[i][l], t, -cost);
    }
  }
  ret += graph.maxflow(s, t);
  auto y = graph.mincut(s);
  std::vector<int> sol(n, k - 1);
  for (int i = 0; i < n; i++)
    for (int l = 0; l < k - 1; l++)
      if (!y[x[i][l]]) sol[i] = l, l = k;
  return std::make_pair(ret, sol);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<long long> B(N), C(N);
  for (int i = 0; i < N; i++) cin >> B[i] >> C[i];
  int M;
  cin >> M;
  vector<vector<bool>> to(N, vector<bool>(N, false));
  for (int i = 0; i < M; i++) {
    int D, E;
    cin >> D >> E;
    to[D][E] = true;
  }
  const long long INF = LLONG_MAX;
  auto theta = [&](int i, int k) {
    if (k == 0) return -C[i];
    if (k == 1) return 0ll;
    return -B[i];
  };
  auto phi = [&](int i, int j, int k, int l) {
    if (to[i][j] && k == 2 && l == 0) return INF;
    return 0ll;
  };
  using MF = MaxFlow<Dinic<long long>>;
  auto [ans, x] = monge_mincut<long long, MF>(N, 3, theta, phi);
  cout << -ans << '\n';
  return 0;
}
0