opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。
競プロで言うところの「燃やす埋める」
問題概要
のグリッドがあって、各マス には整数 が書かれている (負数もある)。
今、横何列かと、縦何列かを選んで色を塗る。色が塗られたマスに書かれた整数の総和を最大化したい。
ただし、ある負数のマスが存在して、横方向からも縦方向からも選ぶような状態は禁じる。
制約
考えたこと
いかにもフローっぽい。最小カットに帰着できそうな雰囲気を感じるので、簡単のため、最初に をすべて -1 倍して、最小コストを求める問題ということにする。
このとき、
- 横の行を選ぶと特定のコストがかかる (コストが負だと嬉しい)
- 縦の列を選ぶと特定のコストがかかる (コストが負だと嬉しい)
- ただし、行 と列 を同時に選んだとき、
- ならば、 のコストが追加でかかる
- は禁止
というようになっている。いかにも「燃やす埋める」っぽい。
ただし、通常の燃やす埋めるでは、コストは「片方は選ぶが他方は選ばない」というような制約に付随する。そこで、縦の列は選ばない方を基準にして考えることにする。つまり、
- = 1 (行 を選ぶ)、0 (行 を選ばない)
- = 1 (列 を選ばない)、0 (列 を選ぶ)
というように 個の変数 を定める。
整理
まず、相互作用を考えない場合は、次のように考える。ここで、 を行 の値の総和、 を列 の値の総和としている。
ただし、負の値になるのは避けたいので、適宜オフセット値 を乗せて、後から引くことにする。具体的には、最後に を引く。
- に対して、コストは
- に対して、コストは
- に対して、コストは
- に対して、コストは
さらに、相互作用は次のように考える。
- のとき: かつ に対して、 のペナルティ
- のとき: かつ に対して、INF のペナルティ
これを元に「燃やす埋める」のグラフを構築して、最小カットを求めればよい。そして、 を引いて、 倍すれば答えが求められる。
コード
#include <bits/stdc++.h> using namespace std; using pint = pair<int, int>; using pll = pair<long long, long long>; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define REP(i, n) for (long long i = 0; i < (long long)(n); ++i) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); ++i) #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, 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, 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, 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, set<T> P) { for(auto it : P) { s << "<" << it << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } // edge class (for network-flow) template<class FLOWTYPE> struct Edge { int rev, from, to; FLOWTYPE cap, icap; Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {} friend ostream& operator << (ostream& s, const Edge& E) { if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')'; else return s; } }; // graph class (for network-flow) template<class FLOWTYPE> struct Graph { vector<vector<Edge<FLOWTYPE> > > list; Graph(int n = 0) : list(n) { } void init(int n = 0) { list.clear(); list.resize(n); } void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; } inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; } inline const size_t size() const { return list.size(); } inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } void addedge(int from, int to, FLOWTYPE cap) { list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap)); list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0)); } void add_undirected_edge(int from, int to, FLOWTYPE cap) { list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap)); list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap)); } /* // debug friend ostream& operator << (ostream& s, const Graph& G) { s << endl; for (int i = 0; i < G.size(); ++i) { s << i << " : " << G.list[i] << endl; } return s; } */ }; template<class FLOWTYPE> struct Dinic { const FLOWTYPE INF = 1LL<<50; // to be set vector<int> level, iter; Dinic() { } void dibfs(Graph<FLOWTYPE> &G, int s) { 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 (int i = 0; i < G[v].size(); ++i) { Edge<FLOWTYPE> &e = G[v][i]; if (level[e.to] < 0 && e.cap > 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } FLOWTYPE didfs(Graph<FLOWTYPE> &G, int v, int t, FLOWTYPE f) { if (v == t) return f; for (int &i = iter[v]; i < G[v].size(); ++i) { Edge<FLOWTYPE> &e = G[v][i], &re = G.redge(e); if (level[v] < level[e.to] && e.cap > 0) { FLOWTYPE d = didfs(G, e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; re.cap += d; return d; } } } return 0; } FLOWTYPE solve(Graph<FLOWTYPE> &G, int s, int t) { level.assign((int)G.size(), -1); iter.assign((int)G.size(), 0); FLOWTYPE res = 0; while (true) { dibfs(G, s); if (level[t] < 0) return res; for (int i = 0; i < (int)iter.size(); ++i) iter[i] = 0; FLOWTYPE flow = 0; while ((flow = didfs(G, s, t, INF)) > 0) { res += flow; } } } }; const long long INF = 1LL<<50; int main() { // 入力 int H, W; cin >> H >> W; 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]; A[i][j] = -A[i][j]; } long long B = 0; vector<long long> S(H + W, 0); for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) S[i] += A[i][j]; for (int j = 0; j < W; ++j) for (int i = 0; i < H; ++i) S[j+H] += A[i][j]; for (int i = 0; i < H + W; ++i) B = min(B, S[i]); B = -B; // グラフを構築 int source = H + W, sink = H + W + 1; Graph<long long> G(H + W + 2); for (int i = 0; i < H; ++i) { G.addedge(source, i, B); G.addedge(i, sink, B + S[i]); } for (int j = 0; j < W; ++j) { G.addedge(source, j+H, B + S[j+H]); G.addedge(j+H, sink, B); } for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { long long cost = (A[i][j] <= 0 ? -A[i][j] : INF); G.addedge(i, j+H, cost); } } Dinic<long long> dinic; long long flow = dinic.solve(G, source, sink); long long res = -(flow - B * (H + W)); cout << res << endl; }