結果
| 問題 | No.119 旅行のツアーの問題 |
| ユーザー |
 hashiryo
|
| 提出日時 | 2021-12-16 16:38:39 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 7,870 bytes |
| コンパイル時間 | 2,772 ms |
| コンパイル使用メモリ | 229,256 KB |
| 実行使用メモリ | 4,352 KB |
| 最終ジャッジ日時 | 2023-10-11 14:55:07 |
| 合計ジャッジ時間 | 4,337 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,352 KB |
| testcase_01 | AC | 2 ms
4,352 KB |
| testcase_02 | AC | 1 ms
4,348 KB |
| testcase_03 | AC | 1 ms
4,352 KB |
| testcase_04 | AC | 2 ms
4,352 KB |
| testcase_05 | AC | 2 ms
4,352 KB |
| testcase_06 | AC | 2 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,352 KB |
| testcase_08 | AC | 2 ms
4,352 KB |
| testcase_09 | AC | 1 ms
4,348 KB |
| testcase_10 | AC | 1 ms
4,352 KB |
| testcase_11 | AC | 1 ms
4,352 KB |
| testcase_12 | AC | 2 ms
4,352 KB |
| testcase_13 | AC | 2 ms
4,348 KB |
| testcase_14 | AC | 2 ms
4,348 KB |
| testcase_15 | AC | 2 ms
4,352 KB |
| testcase_16 | AC | 1 ms
4,348 KB |
| testcase_17 | AC | 2 ms
4,348 KB |
| testcase_18 | AC | 1 ms
4,352 KB |
| testcase_19 | AC | 2 ms
4,348 KB |
| testcase_20 | AC | 2 ms
4,348 KB |
| testcase_21 | AC | 1 ms
4,352 KB |
| testcase_22 | AC | 2 ms
4,352 KB |
ソースコード
#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;
}