結果

問題 No.421 しろくろチョコレート
ユーザー kimiyukikimiyuki
提出日時 2016-09-10 00:13:22
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,979 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 82,852 KB
最終ジャッジ日時 2024-11-14 19:48:55
合計ジャッジ時間 1,503 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int maximum_flow_destructive(int, int, std::vector<std::vector<edge_t> >&)':
main.cpp:39:24: error: 'numeric_limits' was not declared in this scope
   39 |         int f = dfs(s, numeric_limits<int>::max());
      |                        ^~~~~~~~~~~~~~
main.cpp:39:39: error: expected primary-expression before 'int'
   39 |         int f = dfs(s, numeric_limits<int>::max());
      |                                       ^~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }

struct edge_t { int to, cap, rev; };
int maximum_flow_destructive(int s, int t, vector<vector<edge_t> > & g) { // ford fulkerson, O(EF)
    int n = g.size();
    vector<bool> used(n);
    function<int (int, int)> dfs = [&](int i, int f) {
        if (i == t) return f;
        used[i] = true;
        for (edge_t & e : g[i]) {
            if (used[e.to] or e.cap <= 0) continue;
            int nf = dfs(e.to, min(f, e.cap));
            if (nf > 0) {
                e.cap -= nf;
                g[e.to][e.rev].cap += nf;
                return nf;
            }
        }
        return 0;
    };
    int result = 0;
    while (true) {
        used.clear(); used.resize(n);
        int f = dfs(s, numeric_limits<int>::max());
        if (f == 0) break;
        result += f;
    }
    return result;
}
void add_edge(vector<vector<edge_t> > & g, int from, int to, int cap) {
    g[from].push_back((edge_t) {   to, cap, int(g[  to].size()    ) });
    g[  to].push_back((edge_t) { from,   0, int(g[from].size() - 1) });
}

const int dy[4] = { -1, 1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };

int main() {
    // input
    int h, w; cin >> h >> w;
    vector<vector<bool> > f = vectors(false, h, w);
    repeat (y,h) repeat (x,w) {
        char c; cin >> c;
        f[y][x] = c != '.';
    }
    // compute
    auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
    vector<vector<edge_t> > g(h * w + 2);
    auto index = [&](int y, int x) { return y * w + x; };
    const int src = h * w;
    const int dst = h * w + 1;
    int white = 0, black = 0;
    repeat (y,h) repeat (x,w) {
        if (not f[y][x]) continue;
        if (y % 2 == x % 2) {
            white += 1;
            add_edge(g, src, index(y, x), 1);
            repeat (i,4) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (not is_on_field(ny, nx)) continue;
                if (not f[ny][nx]) continue;
                add_edge(g, index(y, x), index(ny, nx), 1);
            }
        } else {
            black += 1;
            add_edge(g, index(y, x), dst, 1);
        }
    }
    int flow = maximum_flow_destructive(src, dst, g);
    int ans = 0;
    ans += flow * 100; white -= flow; black -= flow;
    int x = min(white, black); ans += x * 10; white -= x; black -= x;
    ans += max(white, black);
    // output
    cout << ans << endl;
    return 0;
}
0