2 変数劣モジュラ関数の和の最小化! 俗にいう燃やす埋める
問題概要
のグリッドがあって、各マス には値 が記されている。
いくつかのマスに「x」を描いていく。「x」は書かれるマスの左上の角と右下の角を結ぶ線分、および右上の角と左下の角を結ぶ線分の 2 本からなる。したがって、斜め方向に隣接するマスに「x」を描くと、「x」を構成する線分の 1 つがひと続きになる。
(「x」を書いたマスの値の総和) - (バツ印を書くために必要な線分の本数の最小値)
の最大値を求めよ。
制約
考えたこと
各マス に対して、次の 0-1 変数を定義する。
このとき、問題を最小コスト問題に読み替えたときに、次のように考えられる。
- のときコスト がかかり、 のときコスト がかかる
- 斜めに隣接する 2 マス について、 のとき、利得 が得られる
これらは、「2 変数劣モジュラ関数」として定式化できて、最小カット問題に帰着できる。詳しくは次の記事を参照。
構成されるグラフの頂点数は 、辺数は であるから、Dinic 法を用いた場合、計算量は となる。Dinic 法は速いので、実際上は通ると考えられるし、実際通る。
コード
#include <bits/stdc++.h> using namespace std; // 1, 2, 3-variable submodular optimization template<class COST> struct ThreeVariableSubmodularOpt { // constructors ThreeVariableSubmodularOpt() : N(2), S(0), T(0), OFFSET(0) {} ThreeVariableSubmodularOpt(int n, COST inf = 0) : N(n), S(n), T(n + 1), OFFSET(0), INF(inf), list(n + 2) {} // initializer void init(int n, COST inf = 0) { N = n, S = n, T = n + 1; OFFSET = 0, INF = inf; list.assign(N + 2, Edge()); pos.clear(); } // add 1-Variable submodular functioin 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; add_edge(S, xi, false_cost - true_cost); } else { OFFSET += false_cost; add_edge(xi, T, 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); add_edge(xi, xj, INF); } // 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(C >= 0); add_edge(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(P >= 0); OFFSET -= P; add_edge(S, xi, P); 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(P >= 0); OFFSET -= P; add_edge(xj, T, P); 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(B + C >= A + D); // assure submodular function OFFSET += A; add_single_cost(xi, 0, D - B); add_single_cost(xj, 0, B - A); 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 void add_all_true_profit(const vector<int> &xs, COST P) { assert(P >= 0); int y = (int)list.size(); list.resize(y + 1); OFFSET -= P; add_edge(S, y, P); for (auto xi : xs) { assert(xi >= 0 && xi < N); 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 void add_all_false_profit(const vector<int> &xs, COST P) { assert(P >= 0); int y = (int)list.size(); list.resize(y + 1); OFFSET -= P; add_edge(y, T, P); for (auto xi : xs) { assert(xi >= 0 && xi < N); 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() { return dinic() + OFFSET; } // reconstrcut the optimal assignment vector<bool> reconstruct() { vector<bool> res(N, false), seen(list.size(), false); queue<int> que; seen[S] = true; que.push(S); while (!que.empty()) { int v = que.front(); que.pop(); for (const auto &e : list[v]) { if (e.cap && !seen[e.to]) { if (e.to < N) res[e.to] = true; seen[e.to] = true; que.push(e.to); } } } return res; } // debug friend ostream& operator << (ostream& s, const ThreeVariableSubmodularOpt &tvs) { const auto &edges = tvs.get_edges(); for (const auto &e : edges) s << e << endl; return s; } private: // edge class struct Edge { // core members int rev, from, to; COST cap, icap, flow; // constructor Edge(int r, int f, int t, COST c) : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {} void reset() { cap = icap, flow = 0; } // debug friend ostream& operator << (ostream& s, const Edge& E) { return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')'; } }; // inner data int N, S, T; COST OFFSET, INF; vector<vector<Edge>> list; vector<pair<int,int>> pos; // add edge Edge &get_rev_edge(const Edge &e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } Edge &get_edge(int i) { return list[pos[i].first][pos[i].second]; } const Edge &get_edge(int i) const { return list[pos[i].first][pos[i].second]; } vector<Edge> get_edges() const { vector<Edge> edges; for (int i = 0; i < (int)pos.size(); ++i) { edges.push_back(get_edge(i)); } return edges; } void add_edge(int from, int to, COST cap) { if (!cap) return; pos.emplace_back(from, (int)list[from].size()); list[from].push_back(Edge((int)list[to].size(), from, to, cap)); list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0)); } // Dinic's algorithm COST dinic(COST limit_flow) { COST current_flow = 0; vector<int> level((int)list.size(), -1), iter((int)list.size(), 0); // Dinic BFS auto bfs = [&]() -> void { level.assign((int)list.size(), -1); level[S] = 0; queue<int> que; que.push(S); while (!que.empty()) { int v = que.front(); que.pop(); for (const Edge &e : list[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, COST up_flow) { if (v == T) return up_flow; COST res_flow = 0; for (int &i = iter[v]; i < (int)list[v].size(); ++i) { Edge &e = list[v][i], &re = get_rev_edge(e); if (level[v] >= level[e.to] || e.cap == 0) continue; COST 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) { COST flow = dfs(dfs, S, limit_flow - current_flow); if (!flow) break; current_flow += flow; } } return current_flow; }; COST dinic() { return dinic(numeric_limits<COST>::max()); } }; int main() { long long H, W, C; cin >> H >> W >> C; vector<vector<long long>> A(H, vector<long long>(W)); for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> A[i][j]; auto get_id = [&](int i, int j) -> int { return i * W + j; }; // セットアップ (F: × を書かない, T: x を書く) const long long INF = 1LL<<45; ThreeVariableSubmodularOpt<long long> tvs(H * W, INF); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { tvs.add_single_cost(get_id(i, j), 0, C * 2 - A[i][j]); // 斜めに隣接すると、C の利得 if (i+1 < H && j-1 >= 0) { tvs.add_both_true_profit(get_id(i, j), get_id(i+1, j-1), C); } if (i+1 < H && j+1 < W) { tvs.add_both_true_profit(get_id(i, j), get_id(i+1, j+1), C); } } } // 求める long long res = -tvs.solve(); cout << res << endl; }