結果
| 問題 |
No.957 植林
|
| コンテスト | |
| ユーザー |
 hitonanode
|
| 提出日時 | 2025-07-30 22:47:54 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 15,338 bytes |
| コンパイル時間 | 3,356 ms |
| コンパイル使用メモリ | 195,108 KB |
| 実行使用メモリ | 55,728 KB |
| 最終ジャッジ日時 | 2025-07-30 22:48:08 |
| 合計ジャッジ時間 | 13,534 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 TLE * 1 -- * 29 |
ソースコード
#line 1 "flow/test/submodular_opt.yuki957.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/957"
#line 2 "flow/submodular_optimization_via_graph_cut.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <map>
#include <tuple>
#include <utility>
#include <vector>
#include <atcoder/maxflow>
template <class VarName = int, class Cost = long long> 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][(int)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 IfNotAll(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::map<VarName, bool> x;
};
Result Solve() const {
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};
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;
}
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::map<VarName, bool> sol;
for (int i = 0; i < nvar; ++i) {
const bool xi = !min_cut.at(i) ^ flipped.at(i);
sol[to_var_name.at(i)] = xi;
}
return {true, total_cost, sol};
}
};
#line 4 "flow/test/submodular_opt.yuki957.test.cpp"
#include <iostream>
#line 7 "flow/test/submodular_opt.yuki957.test.cpp"
using namespace std;
int main() {
int H, W;
cin >> H >> W;
SubmodularOptimizationViaGraphCut<pair<int, int>> so;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
int G;
cin >> G;
so.Impose({i, j}, true, G);
}
}
for (int i = 0; i < H; ++i) {
int R;
cin >> R;
vector<pair<pair<int, int>, bool>> row;
for (int j = 0; j < W; ++j) row.push_back({{i, j}, true});
so.Impose(-R);
so.IfNotAll(row, R);
}
for (int j = 0; j < W; ++j) {
int C;
cin >> C;
vector<pair<pair<int, int>, bool>> col;
for (int i = 0; i < H; ++i) col.push_back({{i, j}, true});
so.Impose(-C);
so.IfNotAll(col, C);
}
const auto res = so.Solve();
cout << -res.total_cost << '\n';
}