結果
| 問題 | No.2320 Game World for PvP |
| コンテスト | |
| ユーザー |
 drken1215
|
| 提出日時 | 2026-09-29 23:59:22 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 2 ms / 2,000 ms |
| + 862µs | |
| コード長 | 35,808 bytes |
| 記録 | |
| コンパイル時間 | 2,923 ms |
| コンパイル使用メモリ | 358,800 KB |
| 実行使用メモリ | 9,908 KB |
| 最終ジャッジ日時 | 2026-09-29 23:59:39 |
| 合計ジャッジ時間 | 5,080 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 30 |
ソースコード
//
// フローアルゴリズム ほぼ全集
//
#include <bits/stdc++.h>
using namespace std;
//------------------------------//
// Utility
//------------------------------//
using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }
#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
// input stream
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
//------------------------------//
// Max Flow
//------------------------------//
// edge class (for max-flow)
template<class FLOW> struct FlowEdge {
// core members
int rev, from, to;
FLOW cap, icap, flow;
// constructor
constexpr FlowEdge() noexcept = default;
constexpr FlowEdge(int rev, int from, int to, FLOW cap, FLOW rcap = 0)
: rev(rev), from(from), to(to), cap(cap), icap(cap), flow(rcap) {
}
void reset() {
flow -= icap - cap;
cap = icap;
}
// debug
friend ostream& operator << (ostream& s, const FlowEdge& e) {
return s << e.from << " -> " << e.to << " (" << e.cap << ", " << e.flow << ")";
}
};
// graph class (for max-flow)
template<class FLOW> struct FlowGraph {
// core members
vector<vector<FlowEdge<FLOW>>> list;
vector<pair<int,int>> pos; // pos[i] := {vertex, order of list[vertex]} of i-th edge
// constructor
FlowGraph(int n = 0) : list(n) { }
void init(int n = 0) {
list.clear(), list.resize(n);
pos.clear();
}
void resize(int n) {
list.resize(n);
}
void clear() {
list.clear(), pos.clear();
}
// getter
vector<FlowEdge<FLOW>> &operator [] (int i) {
assert(0 <= i && i < (int)list.size());
return list[i];
}
const vector<FlowEdge<FLOW>> &operator [] (int i) const {
assert(0 <= i && i < (int)list.size());
return list[i];
}
size_t size() const noexcept {
return list.size();
}
size_t size_edegs() const noexcept {
return pos.size();
}
FlowEdge<FLOW> &get_rev_edge(const FlowEdge<FLOW> &e) {
return list[e.to][e.rev];
}
const FlowEdge<FLOW> &get_rev_edge(const FlowEdge<FLOW> &e) const {
return list[e.to][e.rev];
}
FlowEdge<FLOW> &get_edge(int i) {
return list[pos[i].first][pos[i].second];
}
const FlowEdge<FLOW> &get_edge(int i) const {
return list[pos[i].first][pos[i].second];
}
vector<FlowEdge<FLOW>> get_edges() const {
vector<FlowEdge<FLOW>> edges;
for (int i = 0; i < (int)pos.size(); ++i) {
edges.push_back(get_edge(i));
}
return edges;
}
// change edges
void reset() const {
for (int i = 0; i < (int)list.size(); ++i) {
for (FlowEdge<FLOW> &e : list[i]) e.reset();
}
}
void change_edge(FlowEdge<FLOW> &e, FLOW new_cap, FLOW new_rcap) {
assert(new_cap >= 0 && new_rcap >= 0);
FlowEdge<FLOW> &re = get_rev_edge(e);
e.cap = new_cap, e.icap = new_cap + new_rcap, e.flow = new_rcap;
re.cap = new_rcap, re.icap = new_cap + new_rcap, re.flow = new_cap;
}
// add_edge
void add_edge(int from, int to, FLOW cap, FLOW rcap = 0) {
assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
assert(cap >= 0);
int from_id = int(list[from].size()), to_id = int(list[to].size());
if (from == to) to_id++;
pos.emplace_back(from, from_id);
list[from].push_back(FlowEdge<FLOW>(to_id, from, to, cap, rcap));
list[to].push_back(FlowEdge<FLOW>(from_id, to, from, rcap, cap));
}
void add_bidirected_edge(int from, int to, FLOW cap) {
assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
assert(cap >= 0);
add_edge(from, to, cap, cap);
}
// augment
FLOW augment(int s, int t, FLOW up_flow = numeric_limits<FLOW>::max()) {
vector<bool> seen(size(), false);
auto dfs = [&](auto &&dfs, int v, FLOW up_flow) -> FLOW {
if (v == t) return up_flow;
seen[v] = true;
for (int i = 0; i < (int)list[v].size(); i++) {
FlowEdge<FLOW> &e = list[v][i], &re = get_rev_edge(e);
if (seen[e.to] || e.cap <= 0) continue;
FLOW flow = dfs(dfs, e.to, min(up_flow, e.cap));
if (flow > 0) {
e.cap -= flow, e.flow += flow;
re.cap += flow, re.flow -= flow;
return flow;
}
}
return FLOW(0);
};
return dfs(dfs, s, up_flow);
};
FLOW augment(int s, int t, vector<FlowEdge<FLOW>> &path, FLOW up_flow = numeric_limits<FLOW>::max()) {
vector<bool> seen(size(), false);
auto dfs = [&](auto &&dfs, int v, vector<FlowEdge<FLOW>> &path, FLOW up_flow) -> FLOW {
if (v == t) return up_flow;
seen[v] = true;
for (int i = 0; i < (int)list[v].size(); i++) {
FlowEdge<FLOW> &e = list[v][i], &re = get_rev_edge(e);
if (seen[e.to] || e.cap <= 0) continue;
FLOW flow = dfs(dfs, e.to, path, min(up_flow, e.cap));
if (flow > 0) {
e.cap -= flow, e.flow += flow;
re.cap += flow, re.flow -= flow;
path.emplace_back(e);
return flow;
}
}
return FLOW(0);
};
path.clear();
FLOW res = dfs(dfs, s, path, up_flow);
reverse(path.begin(), path.end());
return res;
};
// find reachable nodes from node s (1: s-domain, -1: t-domain, 0: no reach)
vector<int> find_cut(int s, int t) const {
vector<int> res(size(), 0);
auto dfs_s = [&](auto &&dfs_s, int v) -> void {
res[v] = 1;
for (const auto &e : list[v]) {
if (res[e.to] || e.cap <= 0) continue;
dfs_s(dfs_s, e.to);
}
};
auto dfs_t = [&](auto &&dfs_t, int v) -> void {
res[v] = -1;
for (const auto &e : list[v]) {
auto re = get_rev_edge(e);
if (res[e.to] || re.cap <= 0) continue;
dfs_t(dfs_t, e.to);
}
};
dfs_s(dfs_s, s), dfs_t(dfs_t, t);
return res;
}
// finc cutset
vector<FlowEdge<FLOW>> find_cutset(int s, int t) const {
vector<int> cut = find_cut(s, t);
vector<FlowEdge<FLOW>> res;
const auto &edges = get_edges();
for (const auto &e : edges) {
if (cut[e.from] == 1 && cut[e.to] != 1) {
res.emplace_back(e);
}
}
return res;
}
// check if the s-t flow is feasible
bool is_feasible(int s, int t) const {
vector<FLOW> b(list.size(), FLOW(0));
for (int v = 0; v < (int)list.size(); v++) {
for (const auto &e : list[v]) {
b[v] += (e.flow - get_rev_edge(e).flow) / 2;
}
}
if (b[s] + b[t] != 0) return false;
for (int v = 0; v < (int)list.size(); v++) {
if (v != s && v != t && b[v] != FLOW(0)) return false;
}
return true;
}
bool is_feasible(int s, int t, FLOW flow) const {
vector<FLOW> b(list.size(), FLOW(0));
for (int v = 0; v < (int)list.size(); v++) {
for (const auto &e : list[v]) {
b[v] += (e.flow - get_rev_edge(e).flow) / 2;
}
}
if (b[s] != flow) return false;
if (b[t] != -flow) return false;
for (int v = 0; v < (int)list.size(); v++) {
if (v != s && v != t && b[v] != FLOW(0)) return false;
}
return true;
}
// decompose flow into s-t simple paths and cycles
using Path = vector<FlowEdge<FLOW>>;
pair<vector<Path>, vector<Path>> decompose(int s, int t) const {
struct Arc {
int to;
FLOW rem;
int eidx;
};
assert(is_feasible(s, t));
vector<vector<Arc>> fg(list.size());
for (int v = 0; v < (int)list.size(); v++) {
for (int j = 0; j < (int)list[v].size(); j++) {
FLOW f = list[v][j].icap - list[v][j].cap;
if (f > 0) fg[v].push_back({list[v][j].to, f, j});
}
}
vector<int> ptr(list.size(), 0), onpath(list.size(), -1);
vector<pair<int, int>> route;
vector<int> used;
vector<Path> paths, cycles;
auto next_arc = [&](int v) -> int {
while (ptr[v] < (int)fg[v].size() && fg[v][ptr[v]].rem <= 0) ptr[v]++;
return (ptr[v] < (int)fg[v].size() ? ptr[v] : -1);
};
auto extract = [&](int begin, bool is_cycle) {
FLOW mi = numeric_limits<FLOW>::max();
for (int k = begin; k < (int)route.size(); k++) {
auto [v, i] = route[k];
mi = min(mi, fg[v][i].rem);
}
vector<FlowEdge<FLOW>> seq;
for (int k = begin; k < (int)route.size(); k++) {
auto [v, i] = route[k];
fg[v][i].rem -= mi;
FlowEdge<FLOW> e = list[v][fg[v][i].eidx];
e.flow = mi;
seq.push_back(e);
}
if (is_cycle) cycles.push_back(std::move(seq));
else paths.push_back(std::move(seq));
};
auto walk = [&](int start, bool stop_at_t) {
route.clear();
int v = start;
onpath[v] = 0;
used.push_back(v);
while (true) {
int i = next_arc(v), u = fg[v][i].to;
route.push_back({v, i});
if (stop_at_t && u == t) {
extract(0, false);
break;
}
if (onpath[u] != -1) {
extract(onpath[u], true);
break;
}
onpath[u] = (int)route.size();
used.push_back(u);
v = u;
}
for (int w : used) onpath[w] = -1;
used.clear();
};
// extract all s-t paths
while (next_arc(s) != -1) walk(s, true);
// decompose remained circulation into cycles
for (int v = 0; v < (int)list.size(); v++) while (next_arc(v) != -1) walk(v, false);
return {paths, cycles};
}
// debug
friend ostream& operator << (ostream& s, const FlowGraph &G) {
const auto &edges = G.get_edges();
for (const auto &e : edges) s << e << endl;
return s;
}
};
// Dinic
template<class FLOW> FLOW Dinic(FlowGraph<FLOW> &G, int s, int t, FLOW limit_flow) {
assert(0 <= s && s < G.size() && 0 <= t && t < G.size() && s != t);
FLOW current_flow = 0;
vector<int> level((int)G.size(), -1), iter((int)G.size(), 0);
// Dinic BFS
auto bfs = [&]() -> void {
level.assign((int)G.size(), -1);
level[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (const FlowEdge<FLOW> &e : G[v]) {
if (level[e.to] < 0 && e.cap > 0) {
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
}
};
// Dinic DFS
auto dfs = [&](auto self, int v, FLOW up_flow) {
if (v == t) return up_flow;
FLOW res_flow = 0;
for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
FlowEdge<FLOW> &e = G[v][i], &re = G.get_rev_edge(e);
if (level[v] >= level[e.to] || e.cap <= 0) continue;
FLOW flow = self(self, e.to, min(up_flow - res_flow, e.cap));
if (flow <= 0) continue;
res_flow += flow;
e.cap -= flow, e.flow += flow;
re.cap += flow, re.flow -= flow;
if (res_flow == up_flow) break;
}
return res_flow;
};
// flow
while (current_flow < limit_flow) {
bfs();
if (level[t] < 0) break;
iter.assign((int)iter.size(), 0);
while (current_flow < limit_flow) {
FLOW flow = dfs(dfs, s, limit_flow - current_flow);
if (flow <= 0) break;
current_flow += flow;
}
}
return current_flow;
};
template<class FLOW> FLOW Dinic(FlowGraph<FLOW> &G, int s, int t) {
return Dinic(G, s, t, numeric_limits<FLOW>::max());
}
// Push-Relabel
// we can skip 2nd phase if we should know only about maxflow and residual graph
template<class FLOW> FLOW PushRelabel
(FlowGraph<FLOW> &G, int s, int t, FLOW limit_flow, bool do_2nd_phase = false) {
assert(0 <= s && s < (int)G.size());
assert(0 <= t && t < (int)G.size());
assert(s != t);
const int GlobalRelabelRreq = 5;
const bool UseGapRelabeling = true;
struct PushQueue {
vector<pair<int, int>> even, odd;
int num_even, num_odd;
void init(int N) { even.resize(N), odd.resize(N), num_even = num_odd = 0; }
void clear() { num_even = num_odd = 0; }
int size() const { return num_even + num_odd; }
bool empty() const { return size() == 0; }
int highest() const {
int a = (num_even > 0 ? even[num_even - 1].second : -1);
int b = (num_odd > 0 ? odd[num_odd - 1].second : -1);
return (a > b ? a : b);
}
void push(int v, int h) {
if (h & 1) odd[num_odd++] = {v, h};
else even[num_even++] = {v, h};
}
int pop() {
if (num_even == 0 || (num_odd > 0 && odd[num_odd - 1].second > even[num_even - 1].second)) {
return odd[--num_odd].first;
} else {
return even[--num_even].first;
}
}
} push_que;
int gap, N = (int)G.size();
vector<int> dist, dcnt;
vector<FLOW> excess;
// heuristics
auto global_relabeling = [&](int t) -> void {
push_que.clear();
if (UseGapRelabeling) gap = 1, dcnt.assign(N + 1, 0);
dist.assign(N, N);
dist[t] = 0;
static vector<int> que;
if (que.empty()) que.resize(N);
que[0] = t;
int qb = 0, qe = 1;
while (qb < qe) {
int now = que[qb++];
if (UseGapRelabeling) gap = dist[now] + 1, dcnt[dist[now]]++;
if (excess[now] > 0) push_que.push(now, dist[now]);
for (const auto &e : G[now]) {
if (G.get_rev_edge(e).cap > 0 && dist[e.to] == N) {
dist[e.to] = dist[now] + 1;
while ((int)que.size() <= qe) que.emplace_back(0);
que[qe++] = e.to;
}
}
}
};
// push
auto push = [&](int v, FlowEdge<FLOW> &e) -> void {
auto &re = G.get_rev_edge(e);
FLOW delta = e.cap < excess[v] ? e.cap : excess[v];
excess[v] -= delta, e.cap -= delta, e.flow += delta;
excess[e.to] += delta, re.cap += delta, re.flow -= delta;
if (excess[e.to] > 0 && excess[e.to] <= delta) {
if (!UseGapRelabeling || dist[e.to] <= gap) push_que.push(e.to, dist[e.to]);
}
};
// run
auto run = [&](int t) -> void {
global_relabeling(t);
int tick = (int)G.pos.size() * GlobalRelabelRreq;
while (!push_que.empty()) {
int v = push_que.pop();
if (UseGapRelabeling && dist[v] > gap) continue;
int dnex = N * 2 - 1;
for (auto &e : G[v]) {
if (e.cap <= 0) continue;
if (dist[e.to] == dist[v] - 1) {
push(v, e);
if (excess[v] <= 0) break;
} else {
if (dist[e.to] + 1 < dnex) dnex = dist[e.to] + 1;
}
}
if (excess[v] > 0) {
if (UseGapRelabeling) {
if (dnex != dist[v] && dcnt[dist[v]] == 1 && dist[v] < gap) gap = dist[v];
if (dnex == gap) gap++;
while (push_que.highest() > gap) push_que.pop();
if (dnex > gap) dnex = N;
if (dist[v] != dnex) dcnt[dist[v]]--, dcnt[dnex]++;
}
dist[v] = dnex;
if (!UseGapRelabeling || dist[v] < gap) push_que.push(v, dist[v]);
}
if (GlobalRelabelRreq && --tick == 0) {
tick = (int)G.pos.size() * GlobalRelabelRreq;
global_relabeling(t);
}
}
};
// 1st phase: find preflow
excess.assign(N, 0), dist.assign(N, 0);
excess[s] += limit_flow, excess[t] -= limit_flow;
dist[s] = N;
if (UseGapRelabeling) gap = 1, dcnt.assign(N + 1, 0), dcnt[0] = N - 1;
push_que.init(N);
for (auto &e : G[s]) push(s, e);
run(t);
FLOW res = excess[t] + limit_flow;
// 2nd phase: convert preflow into flow
if (do_2nd_phase) {
excess[s] += excess[t], excess[t] = 0;
global_relabeling(s);
run(s);
assert(excess == vector<FLOW>(N, 0));
}
return res;
}
template<class FLOW> FLOW PushRelabel
(FlowGraph<FLOW> &G, int s, int t, bool do_2nd_phase = false) {
return PushRelabel(G, s, t, numeric_limits<FLOW>::max(), do_2nd_phase);
}
//------------------------------//
// Monge Function Minimization
//------------------------------//
/*
N 個の bool 変数 x_0, x_1, ..., x_{N-1} について、以下の形のコストが定められたときの最小コストを求める
・1 変数 xi に関するコスト (1 変数劣モジュラ関数)
xi = F のときのコスト, xi = T のときのコスト
・2 変数 xi, xj 間の関係性についてのコスト (2 変数劣モジュラ関数)
(xi, xj) = (F, F): コスト A
(xi, xj) = (F, T): コスト B
(xi, xj) = (T, F): コスト C
(xi, xj) = (T, T): コスト D
(ただし、B + C >= A + D でなければならない)
・よくある例は、A = B = D = 0, C >= 0 の形である (特に関数化している)
・この場合は、特に Project Selection Problem と呼ばれ、俗に「燃やす埋める」などとも呼ばれる
・xi = T, xj = F のときにコスト C がかかる
・他に面白い例として、A = B = C = 0, D <= 0 の形もある (これも関数化している)
・xi = T, xj = T のときに (-D) の利得が得られる
・3 変数 xi, xj, xk 間の関係性についてのコスト (3 変数劣モジュラ関数)
(xi, xj, xk) = (F, F, F): コスト A
(xi, xj, xk) = (F, F, T): コスト B
(xi, xj, xk) = (F, T, F): コスト C
(xi, xj, xk) = (F, T, T): コスト D
(xi, xj, xk) = (T, F, F): コスト E
(xi, xj, xk) = (T, F, T): コスト F
(xi, xj, xk) = (T, T, F): コスト G
(xi, xj, xk) = (T, T, T): コスト H
*/
// submodular optimization
template<class COST> struct ThreeVariableSubmodularOpt {
// Graph
int N, S, T;
COST OFFSET, INF;
FlowGraph<COST> G;
// constructors
ThreeVariableSubmodularOpt() : N(2), S(0), T(0), OFFSET(0) {}
ThreeVariableSubmodularOpt(int n, COST inf = numeric_limits<COST>::max() / 2)
: N(n), S(n), T(n + 1), OFFSET(0), INF(inf), G(n + 2) {}
// initializer
void init(int n, COST inf = numeric_limits<COST>::max() / 2) {
N = n, S = n, T = n + 1;
OFFSET = 0, INF = inf;
G.init(N + 2);
}
// add constant cost
void add_cost(COST cost) {
OFFSET += cost;
}
// add 1-variable submodular function
void add_single_cost(int xi, COST false_cost, COST true_cost) {
assert(0 <= xi && xi < N);
if (false_cost >= true_cost) {
OFFSET += true_cost;
if (false_cost - true_cost > 0) G.add_edge(S, xi, false_cost - true_cost);
} else {
OFFSET += false_cost;
G.add_edge(xi, T, true_cost - false_cost);
}
}
void add_single_cost_01(int xi, COST false_cost, COST true_cost) {
add_single_cost(xi, false_cost, true_cost);
}
void add_single_cost_10(int xi, COST false_cost, COST true_cost) {
add_single_cost(xi, true_cost, false_cost);
}
// add "project selection" constraint
// xi = T, xj = F: strictly prohibited
void add_psp_constraint(int xi, int xj) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
G.add_edge(xi, xj, INF);
}
void add_psp_constraint_01(int xi, int xj) {
add_psp_constraint(xj, xi);
}
void add_psp_constraint_10(int xi, int xj) {
add_psp_constraint(xi, xj);
}
// add "project selection" penalty
// xi = T, xj = F: cost C
void add_psp_penalty(int xi, int xj, COST C) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(C >= 0);
if (C > 0) G.add_edge(xi, xj, C);
}
void add_psp_penalty_01(int xi, int xj, COST C) {
add_psp_penalty(xj, xi, C);
}
void add_psp_penalty_10(int xi, int xj, COST C) {
add_psp_penalty(xi, xj, C);
}
// add both True profit
// xi = T, xj = T: profit P (cost -P)
void add_both_true_profit(int xi, int xj, COST P) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(P >= 0);
OFFSET -= P;
if (P > 0) G.add_edge(S, xi, P);
if (P > 0) G.add_edge(xi, xj, P);
}
// add both False profit
// xi = F, xj = F: profit P (cost -P)
void add_both_false_profit(int xi, int xj, COST P) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(P >= 0);
OFFSET -= P;
if (P > 0) G.add_edge(xj, T, P);
if (P > 0) G.add_edge(xi, xj, P);
}
// add general 2-variable submodular function
// (xi, xj) = (F, F): A, (F, T): B
// (xi, xj) = (T, F): C, (T, T): D
void add_submodular_function(int xi, int xj, COST A, COST B, COST C, COST D) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(B + C >= A + D); // assure submodular function
OFFSET += A;
add_single_cost(xi, 0, D - B);
add_single_cost(xj, 0, B - A);
if (B + C - A - D > 0) add_psp_penalty(xi, xj, B + C - A - D);
}
// add all True profit
// y = F: not gain profit (= cost is P), T: gain profit (= cost is 0)
// y: T, xi: F is prohibited
template<class INT> void add_all_true_profit(const vector<INT> &xs, COST P) {
assert(P >= 0);
OFFSET -= P;
int y = (int)G.size();
G.resize(y + 1);
G.add_edge(S, y, P);
for (auto xi : xs) {
assert(xi >= 0 && xi < N);
G.add_edge(y, xi, INF);
}
}
// add all False profit
// y = F: gain profit (= cost is 0), T: not gain profit (= cost is P)
// xi = T, y = F is prohibited
template<class INT> void add_all_false_profit(const vector<INT> &xs, COST P) {
assert(P >= 0);
OFFSET -= P;
int y = (int)G.size();
G.resize(y + 1);
G.add_edge(y, T, P);
for (auto xi : xs) {
assert(xi >= 0 && xi < N);
G.add_edge(xi, y, INF);
}
}
// add general 3-variable submodular function
// (xi, xj, xk) = (F, F, F): cost A
// (xi, xj, xk) = (F, F, T): cost B
// (xi, xj, xk) = (F, T, F): cost C
// (xi, xj, xk) = (F, T, T): cost D
// (xi, xj, xk) = (T, F, F): cost E
// (xi, xj, xk) = (T, F, T): cost F
// (xi, xj, xk) = (T, T, F): cost G
// (xi, xj, xk) = (T, T, T): cost H
void add_submodular_function(int xi, int xj, int xk,
COST A, COST B, COST C, COST D,
COST E, COST F, COST G, COST H) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(0 <= xk && xk < N);
COST P = (A + D + F + G) - (B + C + E + H);
COST P12 = (C + E) - (A + G), P13 = (D + G) - (C + H);
COST P21 = (D + F) - (B + H), P23 = (B + C) - (A + D);
COST P31 = (B + E) - (A + F), P32 = (F + G) - (E + H);
assert(P12 >= 0 && P21 >= 0);
assert(P23 >= 0 && P32 >= 0);
assert(P31 >= 0 && P13 >= 0);
if (P >= 0) {
OFFSET += A;
add_single_cost(xi, 0, F - B);
add_single_cost(xj, 0, G - E);
add_single_cost(xk, 0, D - C);
add_psp_penalty(xj, xi, P12);
add_psp_penalty(xk, xj, P23);
add_psp_penalty(xi, xk, P31);
add_all_true_profit({xi, xj, xk}, P);
} else {
OFFSET += H;
add_single_cost(xi, C - G, 0);
add_single_cost(xj, B - D, 0);
add_single_cost(xk, E - F, 0);
add_psp_penalty(xi, xj, P21);
add_psp_penalty(xj, xk, P32);
add_psp_penalty(xk, xi, P13);
add_all_false_profit({xi, xj, xk}, -P);
}
}
// solve
COST solve(const string solver = "dinic") {
if (solver == "dinic") return Dinic(G, S, T) + OFFSET;
return COST(0);
}
// reconstrcut the optimal assignment
vector<bool> reconstruct() {
vector<bool> res(N, false), seen(G.size(), false);
queue<int> que;
seen[S] = true;
que.push(S);
while (!que.empty()) {
int v = que.front();
que.pop();
for (const auto &e : G[v]) {
if (e.cap > 0 && !seen[e.to]) {
if (e.to < N) res[e.to] = true;
seen[e.to] = true;
que.push(e.to);
}
}
}
return res;
}
// debug
vector<FlowEdge<COST>> get_edges() const {
return G.get_edges();
}
friend ostream& operator << (ostream& s, const ThreeVariableSubmodularOpt &opt) {
const auto &edges = opt.get_edges();
for (const auto &e : edges) s << e << endl;
return s;
}
};
// K-value Two Variable Monge Function Optimization
/*
X[i] = 0, 1, ..., K-1 -> (x[i][1], ..., x[i][K-1])
set X[i] <= d ⇔ x[i][d] = 1
X[i] = 0 -> (1, 1, 1, ..., 1, 1)
X[i] = 1 -> (0, 1, 1, ..., 1, 1)
X[i] = 2 -> (0, 0, 1, ..., 1, 1)
...
X[i] = K-2 -> (0, 0, 0, ..., 0, 1)
X[i] = K-1 -> (0, 0, 0, ..., 0, 0)
*/
template<class COST> struct TwoVariableMongeOpt {
// inner data
int N, N01;
COST INF;
vector<int> ks; // size of x[i]
vector<vector<int>> x; // index of x[i][k] in normal submodular optimization
ThreeVariableSubmodularOpt<COST> tvs;
// constructors
TwoVariableMongeOpt() {}
TwoVariableMongeOpt(int N, int K, COST inf = numeric_limits<COST>::max() / 2) {
vector<int> ks(N, K);
init(ks, inf);
}
template<class INT> TwoVariableMongeOpt(const vector<INT> &ks, COST inf = numeric_limits<COST>::max() / 2) {
init(ks, inf);
}
template<class INT> void init(const vector<INT> &iks, COST inf = numeric_limits<COST>::max() / 2) {
N = (int)iks.size(), INF = inf, ks = iks, N01 = 0;
x.resize(N);
for (int i = 0; i < N; i++) {
assert(ks[i] >= 2);
x[i].assign(ks[i] - 1, 0);
for (int k = 0; k < ks[i] - 1; k++) x[i][k] = N01++;
}
tvs.init(N01, INF);
for (int i = 0; i < N; i++) {
for (int k = 0; k < ks[i] - 2; k++) {
tvs.add_psp_constraint(x[i][k], x[i][k + 1]);
}
}
}
// add constant cost
void add_cost(COST cost) {
tvs.add_cost(cost);
}
// add 1-variable function
void add_single_cost(int xi, const vector<COST> &cost) {
assert(0 <= xi && xi < N);
assert((int)cost.size() == ks[xi]);
tvs.add_cost(cost[ks[xi] - 1]);
for (int k = 0; k < ks[xi] - 1; k++) {
tvs.add_single_cost(x[xi][k], 0, cost[k] - cost[k + 1]);
}
}
// add 2-variable Monge function
void add_monge_function(int xi, int xj, const vector<vector<COST>> &cost) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert((int)cost.size() == ks[xi]);
assert((int)cost[0].size() == ks[xj]);
vector<COST> icost(ks[xi], 0), jcost(ks[xj], 0);
for (int ki = 0; ki < ks[xi]; ki++) icost[ki] = cost[ki][0];
for (int kj = 1; kj < ks[xj]; kj++) jcost[kj] = cost[ks[xi] - 1][kj] - cost[ks[xi] - 1][0];
add_single_cost(xi, icost);
add_single_cost(xj, jcost);
for (int ki = 0; ki < ks[xi] - 1; ki++) {
for (int kj = 0; kj < ks[xj] - 1; kj++) {
COST c = cost[ki][kj + 1] - cost[ki][kj] - cost[ki + 1][kj + 1] + cost[ki + 1][kj];
assert(c >= 0);
tvs.add_psp_penalty(x[xi][ki], x[xj][kj], c);
}
}
}
// add all smaller profit (x[xs[i]] <= a[i])
template<class INT> void add_all_smaller_profit(const vector<INT> &xs, const vector<INT> &a, COST P) {
assert(xs.size() == a.size());
vector<INT> txs;
for (int i = 0; i < (int)xs.size(); i++) {
assert(a[i] >= 0);
if (a[i] >= ks[xs[i]] - 1) continue;
txs[i].emplace_back(x[xs[i]][a[i]]); // x <= a equals x[a] = True
}
tvs.add_all_true_profit(txs, P);
}
// add all larger profit (x[xs[i]] > a[i])
template<class INT> void add_all_larger_profit(const vector<INT> &xs, const vector<INT> &a, COST P) {
assert(xs.size() == a.size());
vector<INT> txs;
for (int i = 0; i < (int)xs.size(); i++) {
assert(a[i] < ks[xs[i]] - 1);
if (a[i] < 0) continue;
txs.emplace_back(x[xs[i]][a[i]]); // x > a equals x[a] = False
}
tvs.add_all_false_profit(txs, P);
}
// solve
COST solve(const string &solver = "dinic") {
return tvs.solve(solver);
}
// reconstrcut the optimal assignment
vector<int> reconstruct() {
vector<int> res(N, 0);
vector<bool> tres = tvs.reconstruct();
for (int i = 0; i < N; i++) for (int ki = 0; ki < ks[i] - 1; ki++) {
res[i] += not tres[x[i][ki]];
}
return res;
}
// debug
vector<FlowEdge<COST>> get_edges() const {
return tvs.get_edges();
}
friend ostream& operator << (ostream& s, const TwoVariableMongeOpt &opt) {
const auto &edges = opt.get_edges();
for (const auto &e : edges) s << e << endl;
return s;
}
};
//------------------------------//
// Examples
//------------------------------//
int main() {
long long N, S, T, INF = 1LL << 50;
cin >> N >> S >> T;
ThreeVariableSubmodularOpt<long long> opt(N);
vector<long long> E(S), R(T);
for (int i = 0; i < S; i++) cin >> E[i], E[i]--, opt.add_single_cost_10(E[i], 0, INF);
for (int i = 0; i < T; i++) cin >> R[i], R[i]--, opt.add_single_cost_10(R[i], INF, 0);
vector<vector<long long>> C(N, vector<long long>(N));
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
cin >> C[i][j];
if (i < j) opt.add_submodular_function(i, j, -C[i][j], 0, 0, -C[i][j]);
}
cout << -opt.solve() << endl;
}