opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。

競プロで言うところの「燃やす埋める」

問題へのリンク

問題概要

$H \times W$ のグリッドがあって、各マス $(i, j)$ には整数 $A_{i, j}$ が書かれている (負数もある)。

今、横何列かと、縦何列かを選んで色を塗る。色が塗られたマスに書かれた整数の総和を最大化したい。

ただし、ある負数のマスが存在して、横方向からも縦方向からも選ぶような状態は禁じる。

制約

$1 \le H, W \le 100$
$-10^{9} \le A_{i, j} \le 10^{9}$

考えたこと

いかにもフローっぽい。最小カットに帰着できそうな雰囲気を感じるので、簡単のため、最初に $A_{i, j}$ をすべて -1 倍して、最小コストを求める問題ということにする。

このとき、

横の行を選ぶと特定のコストがかかる (コストが負だと嬉しい)
縦の列を選ぶと特定のコストがかかる (コストが負だと嬉しい)
ただし、行と列を同時に選んだとき、
- $A_{i, j} \le 0$ ならば、 $-A_{i, j}$ のコストが追加でかかる
- $A_{i, j} \gt 0$ は禁止

というようになっている。いかにも「燃やす埋める」っぽい。

ただし、通常の燃やす埋めるでは、コストは「片方は選ぶが他方は選ばない」というような制約に付随する。そこで、縦の列は選ばない方を基準にして考えることにする。つまり、

$x_{i}$ = 1 (行 $i$ を選ぶ)、0 (行 $i$ を選ばない)
$x_{j+H}$ = 1 (列 $j$ を選ばない)、0 (列 $j$ を選ぶ)

というように $H+W$ 個の変数 $x_{0}, \dots, x_{H+W-1}$ を定める。

整理

まず、相互作用を考えない場合は、次のように考える。ここで、 $S_{i}$ を行 $i$ の値の総和、 $S_{j+H}$ を列 $j$ の値の総和としている。

ただし、負の値になるのは避けたいので、適宜オフセット値 $B$ を乗せて、後から引くことにする。具体的には、最後に $B(H+W)$ を引く。

$x_{i} = 1$ に対して、コストは $B + S_{i}$
$x_{i} = 0$ に対して、コストは $B$
$x_{j+H} = 1$ に対して、コストは $B$
$x_{j+H} = 0$ に対して、コストは $B + S_{j+H}$

さらに、相互作用は次のように考える。

$A_{i, j} \le 0$ のとき： $x_{i} = 1$ かつ $x_{j+W} = 0$ に対して、 $-A_{i, j}$ のペナルティ
$A_{i, j} \gt 0$ のとき： $x_{i} = 1$ かつ $x_{j+W} = 0$ に対して、INF のペナルティ

これを元に「燃やす埋める」のグラフを構築して、最小カットを求めればよい。そして、 $B(H+W)$ を引いて、 $-1$ 倍すれば答えが求められる。

コード

#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;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 259 G - Grid Card Game (橙色, 600 点)

問題概要

制約

考えたこと

整理

コード