結果
| 問題 | No.119 旅行のツアーの問題 |
| ユーザー |
 Forested
|
| 提出日時 | 2024-03-30 23:04:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 5,000 ms |
| コード長 | 6,833 bytes |
| コンパイル時間 | 2,713 ms |
| コンパイル使用メモリ | 217,148 KB |
| 最終ジャッジ日時 | 2025-02-20 16:04:33 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 19 |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/119"// ============#include <atcoder/maxflow>template <typename T>class MongeMinCut {int n;std::vector<int> k;std::vector<int> offset;int s;int t;T all;atcoder::mf_graph<T> graph;T big;void add_v(int v, T f0, T f1) {if (f0 <= f1) {add_0(f0);graph.add_edge(s, v, f1 - f0);} else {add_0(f1);graph.add_edge(v, t, f0 - f1);}}public:MongeMinCut(const std::vector<int> &k, T big): n((int)k.size()),k(k),offset(n, 0),s(0),t(0),all(0),graph(0),big(big) {for (int i = 0; i < n; ++i) {assert(k[i] >= 1);}for (int i = 0; i < n - 1; ++i) {offset[i + 1] = offset[i] + k[i] - 1;}s = 0;for (int i = 0; i < n; ++i) {s += k[i];}t = s + 1;graph = atcoder::mf_graph<T>(s + 2);for (int i = 0; i < n; ++i) {for (int j = 0; j < k[i] - 2; ++j) {graph.add_edge(offset[i] + j + 1, offset[i] + j, big);}}}void add_0(T v) { all += v; }void add_1(int i, const std::vector<T> &f) {assert(0 <= i && i < n && (int)f.size() == k[i]);add_0(f[0]);for (int j = 0; j < k[i] - 1; ++j) {add_v(offset[i] + j, f[j + 1] - f[j], 0);}}void add_2(int x, int y, std::vector<std::vector<T>> f) {assert(0 <= x && x < n);assert(0 <= y && y < n);assert((int)f.size() == k[x]);for (int i = 0; i < k[x]; ++i) {assert((int)f[i].size() == k[y]);}std::vector<T> tmp(k[x]);for (int i = 0; i < k[x]; ++i) {tmp[i] = f[i][0];}add_1(x, tmp);for (int i = 0; i < k[x]; ++i) {for (int j = 0; j < k[y]; ++j) {f[i][j] -= tmp[i];}}tmp = f[0];add_1(y, tmp);for (int i = 0; i < k[x]; ++i) {for (int j = 0; j < k[y]; ++j) {f[i][j] -= tmp[j];}}for (int i = 0; i < k[x] - 1; ++i) {for (int j = 0; j < k[y] - 1; ++j) {T val = f[i][j] + f[i + 1][j + 1] - f[i + 1][j] - f[i][j + 1];assert(val <= 0);add_0(val);graph.add_edge(offset[x] + i, offset[y] + j, -val);graph.add_edge(s, offset[x] + i, -val);}}}std::pair<T, std::vector<int>> solve() {T cost = graph.flow(s, t) + all;std::vector<bool> cut = graph.min_cut(s);std::vector<int> ans(n, 0);for (int i = 0; i < n; ++i) {for (int j = 0; j < k[i] - 1; ++j) {if (cut[offset[i] + j]) {++ans[i];}}}return std::pair<T, std::vector<int>>(cost, ans);}};// ============// ============#include <bits/stdc++.h>#define OVERRIDE(a, b, c, d, ...) d#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)#define ALL(x) begin(x), end(x)#define LEN(x) (i32)(x.size())using namespace std;using u32 = unsigned int;using u64 = unsigned long long;using i32 = signed int;using i64 = signed long long;using f64 = double;using f80 = long double;using pi = pair<i32, i32>;using pl = pair<i64, i64>;template <typename T>using V = vector<T>;template <typename T>using VV = V<V<T>>;template <typename T>using VVV = V<V<V<T>>>;template <typename T>using VVVV = V<V<V<V<T>>>>;template <typename T>using PQR = priority_queue<T, V<T>, greater<T>>;template <typename T>bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}template <typename T>i32 lob(const V<T> &arr, const T &v) {return (i32)(lower_bound(ALL(arr), v) - arr.begin());}template <typename T>i32 upb(const V<T> &arr, const T &v) {return (i32)(upper_bound(ALL(arr), v) - arr.begin());}template <typename T>V<i32> argsort(const V<T> &arr) {V<i32> ret(arr.size());iota(ALL(ret), 0);sort(ALL(ret), [&](i32 i, i32 j) -> bool {if (arr[i] == arr[j]) {return i < j;} else {return arr[i] < arr[j];}});return ret;}#ifdef INT128using u128 = __uint128_t;using i128 = __int128_t;#endif[[maybe_unused]] constexpr i32 INF = 1000000100;[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;struct SetUpIO {SetUpIO() {#ifdef FAST_IOios::sync_with_stdio(false);cin.tie(nullptr);#endifcout << fixed << setprecision(15);}} set_up_io;void scan(char &x) { cin >> x; }void scan(u32 &x) { cin >> x; }void scan(u64 &x) { cin >> x; }void scan(i32 &x) { cin >> x; }void scan(i64 &x) { cin >> x; }void scan(string &x) { cin >> x; }template <typename T>void scan(V<T> &x) {for (T &ele : x) {scan(ele);}}void read() {}template <typename Head, typename... Tail>void read(Head &head, Tail &...tail) {scan(head);read(tail...);}#define CHAR(...) \char __VA_ARGS__; \read(__VA_ARGS__);#define U32(...) \u32 __VA_ARGS__; \read(__VA_ARGS__);#define U64(...) \u64 __VA_ARGS__; \read(__VA_ARGS__);#define I32(...) \i32 __VA_ARGS__; \read(__VA_ARGS__);#define I64(...) \i64 __VA_ARGS__; \read(__VA_ARGS__);#define STR(...) \string __VA_ARGS__; \read(__VA_ARGS__);#define VEC(type, name, size) \V<type> name(size); \read(name);#define VVEC(type, name, size1, size2) \VV<type> name(size1, V<type>(size2)); \read(name);// ============int main() {I32(n);V<i32> b(n), c(n);REP(i, n) {read(b[i], c[i]);}I32(m)V<pi> edge(m);for (auto &[u, v] : edge) {read(u, v);}MongeMinCut<i32> mincut(V<i32>(n, 3), INF);REP(i, n) {V<i32> f(3, 0);f[0] = -b[i];f[2] = -c[i];mincut.add_1(i, f);}for (auto [u, v] : edge) {VV<i32> f(3, V<i32>(3, 0));f[0][2] = INF / m;mincut.add_2(u, v, f);}cout << -mincut.solve().first << '\n';}