結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー ferin
提出日時 2019-10-25 15:03:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,825 bytes
コンパイル時間 2,166 ms
コンパイル使用メモリ 185,232 KB
実行使用メモリ 40,832 KB
最終ジャッジ日時 2024-07-19 19:01:19
合計ジャッジ時間 6,076 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 TLE * 1 -- * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

struct min_cost_max_flow {
    struct edge {
        int to;
        ll cap, cost;
        int rev;
        bool isrev;
    };

    int n, s, t;
    ll neg;
    vector<vector<edge>> g;
    vector<ll> d, h, dist, prevv, preve;

    ll flow(vector<ll> d0) {
        ll res = 0;
        priority_queue<PII, vector<PII>, greater<PII>> que;
        h.assign(n, 0);
        preve.assign(n, -1);
        prevv.assign(n, -1);
        ll f = 0;
        REP(i, d.size()) {
            if(i < (ll)d0.size()) d[i] += d0[i];
            if(d[i] > 0) add_edge(s, i, d[i], 0), f += d[i];
            else add_edge(i, t, -d[i], 0);
        }
        while(f > 0) {
            dist.assign(n, INF);
            dist[s] = 0;
            que.push({0, s});
            while(que.size()) {
                PII p = que.top(); que.pop();
                int v = p.second;
                if(dist[v] < p.first) continue;
                REP(i, g[v].size()) {
                    edge &e = g[v][i];
                    if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]) {
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        que.push({dist[e.to], e.to});
                    }
                }
            }
            if(dist[t] == INF) return -1;
            REP(v, n) h[v] += dist[v];
            ll d = f;
            for(int v = t; v != s; v = prevv[v]) {
                chmin(d, g[prevv[v]][preve[v]].cap);
            }
            f -= d; res += d * h[t];
            for(int v = t; v != s; v = prevv[v]) {
                edge &e = g[prevv[v]][preve[v]];
                e.cap -= d;
                g[v][e.rev].cap += d;
            }
        }
        return neg + res;
    }

    min_cost_max_flow(int n0) : n(n0+2), s(n0), t(n0+1), neg(0), g(n0+2), d(n0+2) {}

    void add_edge(int from, int to, ll cap, ll cost) {
        if(cost >= 0) {
            g[from].push_back({to, cap, cost, (int)g[to].size(), true});
            g[to].push_back({from, 0, -cost, (int)g[from].size()-1, false});
        } else {
            d[from] -= cap;
            d[to] += cap;
            neg += cap * cost;
            add_edge(to, from, cap, -cost);
        }
    }

    // SからTに流量fを流す
    // 流せないなら-1
    ll flow(int S, int T, ll f) {
        vector<ll> d0(n);
        d0[S] = f, d0[T] = -f;
        return flow(d0);
    }
};

int main(void) {
    ll h, w;
    cin >> h >> w;
    vector<string> a(h);
    REP(i, h) cin >> a[i];

    min_cost_max_flow graph(h*w+2);
    ll s = h*w, t = s+1, f = 0;

    REP(i, h) REP(j, w) {
        if(a[i][j]=='w') {
            graph.add_edge(s, i*w+j, 1, 0);
            graph.add_edge(i*w+j, t, 1, -1);
            f++;
        } else {
            graph.add_edge(s, i*w+j, 1, -1);
            graph.add_edge(i*w+j, t, 1, 0);
        }
        if(a[i][j]!='w') continue;
        REP(y, h) REP(x, w) {
            if(a[y][x]!='b') continue;
            if(abs(y-i)+abs(x-j) == 1) {
                graph.add_edge(i*w+j, y*w+x, 1, -100);
            } else {
                graph.add_edge(i*w+j, y*w+x, 1, -10);
            }
        }
    }

    cout << -graph.flow(s, t, f) << endl;

    return 0;
}
0