結果
| 問題 |
No.3201 Corporate Synergy
|
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2025-07-30 22:06:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 22,488 bytes |
| コンパイル時間 | 4,371 ms |
| コンパイル使用メモリ | 294,152 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-07-30 22:06:12 |
| 合計ジャッジ時間 | 5,268 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }
template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr)
#else
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif
#include <atcoder/maxflow>
template <class VarName, class Cost> class SubmodularOptimizationViaGraphCut {
public:
struct Bipartite {
std::vector<std::vector<std::pair<int, bool>>> to;
Bipartite(int nvar) : to(nvar) {}
void Same(int idx1, int idx2) {
to.at(idx1).emplace_back(idx2, false);
to.at(idx2).emplace_back(idx1, false);
}
void Diff(int idx1, int idx2) {
to.at(idx1).emplace_back(idx2, true);
to.at(idx2).emplace_back(idx1, true);
}
std::pair<bool, std::vector<bool>> Coloring() const {
const int nvar = to.size();
std::vector<bool> is_flipped(nvar, false), visited(nvar, false);
bool failed = false;
auto rec = [&](auto &&self, int now) -> void {
visited.at(now) = true;
for (auto [nxt, w] : to.at(now)) {
const bool next_val = is_flipped.at(now) ^ w;
if (visited.at(nxt)) {
if (is_flipped.at(nxt) != next_val) {
failed = true;
return;
}
} else {
is_flipped.at(nxt) = next_val;
self(self, nxt);
}
}
};
for (int i = 0; i < nvar; ++i) {
if (visited.at(i)) continue;
rec(rec, i);
if (failed) return {false, {}};
}
return {true, is_flipped};
}
};
// https://www.acmicpc.net/problem/21768 ?
struct Submodular {
static bool Check(Cost f00, Cost f01, Cost f10, Cost f11) {
return f00 + f11 <= f01 + f10;
}
static bool Check(const std::array<Cost, 4> &f) { return Check(f[0], f[1], f[2], f[3]); }
static bool Check(const std::array<Cost, 8> &f) {
return Check(f[0], f[1], f[2], f[3]) and Check(f[4], f[5], f[6], f[7]) and
Check(f[0], f[1], f[4], f[5]) and Check(f[2], f[3], f[6], f[7]) and
Check(f[0], f[2], f[4], f[6]) and Check(f[1], f[3], f[5], f[7]);
}
};
template <int Size>
static std::array<Cost, Size> Transpose(const std::array<Cost, Size> &f, int flip_mask) {
std::array<Cost, Size> ret;
for (int i = 0; i < Size; ++i) ret.at(i ^ flip_mask) = f.at(i);
return ret;
}
template <int Size> int GetSubmodularFlips(const std::array<Cost, Size> &f) const {
int ret = 0;
for (int flip_mask = 0; flip_mask < (int)f.size(); ++flip_mask) {
if (Submodular::Check(Transpose<Size>(f, flip_mask))) ret |= 1 << flip_mask;
}
return ret;
}
std::map<VarName, int> to_internal_idx;
std::vector<VarName> to_var_name;
Cost f0 = Cost{};
std::map<int, std::array<Cost, 2>> unary;
std::map<std::tuple<int, int>, std::array<Cost, 4>> binary;
std::map<std::tuple<int, int, int>, std::array<Cost, 8>> ternary;
std::map<std::vector<std::pair<int, bool>>, Cost> satisfy_all;
int RegisterOrGetIndex(const VarName &name) {
if (!to_internal_idx.contains(name)) {
to_internal_idx[name] = to_internal_idx.size();
to_var_name.push_back(name);
}
return to_internal_idx.at(name);
}
public:
SubmodularOptimizationViaGraphCut() {}
// Impose constant `cost`
void Impose(Cost cost) { f0 += cost; }
// Impose `cost` when `x == tf`
void Impose(const VarName &x, bool tf, Cost cost) {
const int idx = RegisterOrGetIndex(x);
unary[idx][tf] += cost;
}
// Impose `cost` when `x1 == tf1 and x2 == tf2`
void Impose(const VarName &x1, bool tf1, const VarName &x2, bool tf2, Cost cost) {
int idx1 = RegisterOrGetIndex(x1);
int idx2 = RegisterOrGetIndex(x2);
assert(idx1 != idx2);
if (idx1 > idx2) {
std::swap(idx1, idx2);
std::swap(tf1, tf2);
}
binary[std::make_tuple(idx1, idx2)][(tf1 << 1) | tf2] += cost;
}
// Impose `cost` when `x1 == tf1, x2 == tf2 and x3 == tf3`
void Impose(const VarName &x1, bool tf1, const VarName &x2, bool tf2, const VarName &x3,
bool tf3, Cost cost) {
int idx1 = RegisterOrGetIndex(x1);
int idx2 = RegisterOrGetIndex(x2);
int idx3 = RegisterOrGetIndex(x3);
assert(idx1 != idx2 and idx1 != idx3 and idx2 != idx3);
if (idx1 > idx2) std::swap(idx1, idx2), std::swap(tf1, tf2);
if (idx1 > idx3) std::swap(idx1, idx3), std::swap(tf1, tf3);
if (idx2 > idx3) std::swap(idx2, idx3), std::swap(tf2, tf3);
ternary[std::make_tuple(idx1, idx2, idx3)][(tf1 << 2) | (tf2 << 1) | tf3] += cost;
}
// IntValue [0, k) is represented by (k - 1) variables:
// TTTT...T => 0
// FTTT...T => 1
// FFTT...T => 2
// ...
// FFFF...F => iv.size() (= k - 1)
using IntValue = std::vector<VarName>;
// https://noshi91.hatenablog.com/entry/2021/06/29/044225
void IntValueCost(const IntValue &iv, std::vector<Cost> &costs, Cost inf) {
assert(iv.size() + 1 == costs.size());
for (int i = 1; i < (int)iv.size(); ++i) Then(iv.at(i), false, iv.at(i - 1), false, inf);
const int k = costs.size();
Impose(costs.at(k - 1));
for (int i = k - 2; i >= 0; --i) Impose(iv.at(i), true, costs.at(i) - costs.at(i + 1));
}
// If `iv1 >= min1 and iv2 <= max2` satisfy, impose `cost`
void ImposeLbUb(const IntValue &iv1, int min1, const IntValue &iv2, int max2, Cost cost) {
// iv >= t <=> iv[t - 1] == false or t <= 0
// iv <= t <=> iv[t] == true or t >= iv.size()
if ((int)iv1.size() < min1 or max2 < 0) return;
if (min1 <= 0 and max2 >= (int)iv2.size()) {
Impose(cost);
} else if (min1 <= 0) {
Impose(iv2.at(max2), true, cost);
} else if (max2 >= (int)iv2.size()) {
Impose(iv1.at(min1 - 1), false, cost);
} else {
Impose(iv1.at(min1 - 1), false, iv2.at(max2), true, cost);
}
}
// Impose `penalty` when `(x1 == tf1) => (x2 == tf2)` is NOT satisfied
void Then(const VarName &x1, bool tf1, const VarName &x2, bool tf2, Cost penalty) {
Impose(x1, tf1, x2, !tf2, penalty);
}
// Impose `penalty` when NOT all of `x == tf` in `consts` are satisfied
void RequireAll(const std::vector<std::pair<VarName, bool>> &consts, Cost penalty) {
if (consts.empty()) return;
std::vector<std::pair<int, bool>> internal_vars;
for (const auto &[x, tf] : consts) {
const int idx = RegisterOrGetIndex(x);
internal_vars.emplace_back(idx, tf);
}
std::sort(internal_vars.begin(), internal_vars.end());
internal_vars.erase(
std::unique(internal_vars.begin(), internal_vars.end()), internal_vars.end());
satisfy_all[internal_vars] += penalty;
}
struct Result {
bool feasible = false;
Cost total_cost = Cost{};
std::vector<bool> x = {};
};
Result Solve() const {
dbg(unary);
dbg(binary);
const int nvar = to_internal_idx.size();
Bipartite bp(nvar);
for (const auto &[indices, f] : binary) {
auto [idx1, idx2] = indices;
const int mask = GetSubmodularFlips<4>(f);
if (!mask) return Result{false};
if (!(mask & ((1 << 0b00) | (1 << 0b11)))) bp.Diff(idx1, idx2);
if (!(mask & ((1 << 0b01) | (1 << 0b10)))) bp.Same(idx1, idx2);
}
for (const auto &[indices, f] : ternary) {
auto [idx1, idx2, idx3] = indices;
const int m = GetSubmodularFlips<8>(f);
if (!m) return Result{false};
if (!(m & ((1 << 0b000) | (1 << 0b011) | (1 << 0b100) | (1 << 0b111))))
bp.Diff(idx2, idx3);
if (!(m & ((1 << 0b001) | (1 << 0b010) | (1 << 0b101) | (1 << 0b110))))
bp.Same(idx2, idx3);
if (!(m & ((1 << 0b000) | (1 << 0b101) | (1 << 0b010) | (1 << 0b111))))
bp.Diff(idx1, idx3);
if (!(m & ((1 << 0b001) | (1 << 0b100) | (1 << 0b011) | (1 << 0b110))))
bp.Same(idx1, idx3);
if (!(m & ((1 << 0b000) | (1 << 0b110) | (1 << 0b001) | (1 << 0b111))))
bp.Diff(idx1, idx2);
if (!(m & ((1 << 0b010) | (1 << 0b100) | (1 << 0b011) | (1 << 0b101))))
bp.Same(idx1, idx2);
}
for (const auto &[var_flags, penalty] : satisfy_all) {
if (penalty < Cost{}) return Result{false};
for (auto [idx, tf] : var_flags) {
auto [idx0, tf0] = var_flags.front();
if (tf == tf0) {
bp.Same(idx, idx0);
} else {
bp.Diff(idx, idx0);
}
}
}
Cost base = f0;
std::map<int, Cost> actual_unary;
std::map<std::tuple<int, int>, Cost> actual_binary_ft;
std::map<std::pair<std::vector<int>, bool>, Cost> actual_require_all;
auto ResolveUnary = [&](int idx, const std::array<Cost, 2> &f) {
const Cost f0 = f[0b0], f1 = f[0b1];
base += f0;
actual_unary[idx] += f1 - f0;
};
auto ResolveBinary = [&](int idx1, int idx2, const std::array<Cost, 4> &f) {
const Cost A = f[0b00], B = f[0b01], C = f[0b10], D = f[0b11];
base += A;
ResolveUnary(idx1, {Cost{}, C - A});
ResolveUnary(idx2, {Cost{}, D - C});
const Cost w = (B + C) - (A + D);
assert(w >= Cost{});
if (w > Cost{}) actual_binary_ft[{idx1, idx2}] += w;
};
auto ResolveTernary = [&](int idx1, int idx2, int idx3, const std::array<Cost, 8> &f) {
const Cost A = f[0b000], B = f[0b001], C = f[0b010], D = f[0b011], E = f[0b100],
F = f[0b101], G = f[0b110], H = f[0b111];
const Cost P = (A + D + F + G) - (B + C + E + H);
if (P >= Cost{}) {
base += A;
ResolveUnary(idx1, {Cost{}, F - B});
ResolveUnary(idx2, {Cost{}, G - E});
ResolveUnary(idx3, {Cost{}, D - C});
ResolveBinary(idx2, idx3, {Cost{}, (B + C) - (A + D), Cost{}, Cost{}});
ResolveBinary(idx1, idx3, {Cost{}, Cost{}, (B + E) - (A + F), Cost{}});
ResolveBinary(idx1, idx2, {Cost{}, (C + E) - (A + G), Cost{}, Cost{}});
base -= P;
if (P) { actual_require_all[{std::vector<int>{idx1, idx2, idx3}, true}] += P; }
} else {
base += H;
ResolveUnary(idx1, {C - G, Cost{}});
ResolveUnary(idx2, {B - D, Cost{}});
ResolveUnary(idx3, {E - F, Cost{}});
ResolveBinary(idx2, idx3, {Cost{}, Cost{}, (F + G) - (E + H), Cost{}});
ResolveBinary(idx1, idx3, {Cost{}, (D + G) - (C + H), Cost{}, Cost{}});
ResolveBinary(idx1, idx2, {Cost{}, Cost{}, (D + F) - (B + H), Cost{}});
base += P;
if (P) { actual_require_all[{std::vector<int>{idx1, idx2, idx3}, false}] += -P; }
}
};
const auto [is_bipartite, flipped] = bp.Coloring();
if (!is_bipartite) return Result{false};
dbg(flipped);
for (auto [idx, f] : unary) {
f = Transpose<2>(f, flipped.at(idx));
ResolveUnary(idx, f);
}
for (auto [indices, f] : binary) {
auto [idx1, idx2] = indices;
f = Transpose<4>(f, (flipped.at(idx1) << 1) | flipped.at(idx2));
ResolveBinary(idx1, idx2, f);
}
for (auto [indices, f] : ternary) {
auto [idx1, idx2, idx3] = indices;
f = Transpose<8>(f, (flipped.at(idx1) << 2) | (flipped.at(idx2) << 1) | flipped.at(idx3));
ResolveTernary(idx1, idx2, idx3, f);
}
for (auto &[var_flags, penalty] : satisfy_all) {
assert(var_flags.size());
const auto [idx0, tf0] = var_flags.front();
std::vector<int> vars;
for (const auto &[idx, tf] : var_flags) {
assert((tf ^ flipped.at(idx)) == (tf0 ^ flipped.at(idx0)));
vars.push_back(idx);
}
actual_require_all[{vars, tf0 ^ flipped.at(idx0)}] += penalty;
}
dbg(base);
dbg(actual_unary);
dbg(actual_binary_ft);
dbg(actual_require_all);
const int v_false = nvar + actual_require_all.size();
const int v_true = v_false + 1;
atcoder::mf_graph<Cost> mf(v_true + 1);
for (auto [idx, cost] : actual_unary) {
if (cost > Cost{}) mf.add_edge(v_false, idx, cost);
if (cost < Cost{}) {
base += cost;
mf.add_edge(idx, v_true, -cost);
}
}
for (auto [indices, f] : actual_binary_ft) {
assert(f >= Cost{});
auto [idx1, idx2] = indices;
if (f > Cost{}) mf.add_edge(idx1, idx2, f);
}
int head = nvar;
for (const auto &[var_flags, penalty] : actual_require_all) {
auto [vars, flg] = var_flags;
assert(penalty >= Cost{});
if (flg) {
for (int i : vars) mf.add_edge(i, head, penalty);
mf.add_edge(head++, v_true, penalty);
} else {
for (int i : vars) mf.add_edge(head, i, penalty);
mf.add_edge(v_false, head++, penalty);
}
}
assert(head == v_false);
const Cost flow = mf.flow(v_false, v_true);
const Cost total_cost = base + flow;
auto min_cut = mf.min_cut(v_false);
std::vector<bool> is_true(nvar, false);
for (int i = 0; i < nvar; ++i) is_true.at(i) = !min_cut.at(i) ^ flipped.at(i);
return {true, total_cost, is_true};
}
};
int main() {
int N;
cin >> N;
vector<lint> P(N);
cin >> P;
SubmodularOptimizationViaGraphCut<int, lint> so;
REP(i, N) so.Impose(i, true, -P.at(i));
dbg(so.unary);
constexpr lint inf = 1LL << 55;
int M;
cin >> M;
vector<pint> UV(M);
for (auto &uv : UV) {
cin >> uv.first >> uv.second;
--uv.first, --uv.second;
// dbg(uv);
so.Then(uv.second, true, uv.first, true, inf);
}
int K;
cin >> K;
vector<tuple<int, int, int>> ABS(K);
for (auto &[a, b, s] : ABS) {
cin >> a >> b >> s;
--a, --b;
dbg(make_tuple(a, b, s));
so.Impose(-s);
so.Impose(a, true, b, false, s);
so.Impose(a, false, b, false, s);
so.Impose(a, false, b, true, s);
}
dbg(P);
dbg(UV);
dbg(ABS);
const auto ret = so.Solve();
dbg(ret.feasible);
dbg(ret.total_cost);
dbg(ret.x);
cout << -ret.total_cost << '\n';
// atcoder::mf_graph<lint> mf(N + 2);
// const int gs = N, gt = N + 1;
// lint base_rieki = 0;
// REP(i, N) {
// if (P[i] > 0) {
// base_rieki += P[i];
// mf.add_edge(gs, i, P[i] * 2);
// } else {
// mf.add_edge(i, gt, -P[i] * 2);
// }
// }
// constexpr lint LARGE = 1LL << 55;
// for (auto [u, v] : UV) { mf.add_edge(v, u, LARGE); }
// for (auto [a, b, s] : ABS) {
// base_rieki += s;
// mf.add_edge(a, b, s);
// mf.add_edge(b, a, s);
// mf.add_edge(gs, a, s);
// mf.add_edge(gs, b, s);
// }
// const lint flow = mf.flow(gs, gt);
// dbg(base_rieki);
// dbg(flow);
// cout << base_rieki - flow / 2 << '\n';
}