結果

問題 No.421 しろくろチョコレート
ユーザー f1b_maxbl00d
提出日時 2020-06-08 13:47:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 3,724 bytes
コンパイル時間 2,527 ms
コンパイル使用メモリ 142,636 KB
最終ジャッジ日時 2025-01-11 00:11:47
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 998244353;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
template< typename flow_t >
struct Dinic {
    const flow_t INF;
    struct edge {
        int to;
        flow_t cap;
        int rev;
        bool isrev;
        int idx;
    };
    vector< vector< edge > > graph;
    vector< int > min_cost, iter;
    Dinic(int V) : INF(numeric_limits< flow_t >::max()), graph(V) {}
    void add_edge(int from, int to, flow_t cap, int idx = -1) {
        edge a = { to, cap, (int)graph[to].size(), false, idx };
        graph[from].emplace_back(a);
        a = { from, 0, (int)graph[from].size() - 1, true, idx };
        graph[to].emplace_back(a);
    }
    bool bfs(int s, int t) {
        min_cost.assign(graph.size(), -1);
        queue< int > que;
        min_cost[s] = 0;
        que.push(s);
        while (!que.empty() && min_cost[t] == -1) {
            int p = que.front();
            que.pop();
            for (auto& e : graph[p]) {
                if (e.cap > 0 && min_cost[e.to] == -1) {
                    min_cost[e.to] = min_cost[p] + 1;
                    que.push(e.to);
                }
            }
        }
        return min_cost[t] != -1;
    }
    flow_t dfs(int idx, const int t, flow_t flow) {
        if (idx == t) return flow;
        for (int& i = iter[idx]; i < graph[idx].size(); i++) {
            edge& e = graph[idx][i];
            if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
                flow_t d = dfs(e.to, t, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    flow_t max_flow(int s, int t) {
        flow_t flow = 0;
        while (bfs(s, t)) {
            iter.assign(graph.size(), 0);
            flow_t f = 0;
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
        return flow;
    }
    void output() {
        for (int i = 0; i < graph.size(); i++) {
            for (auto& e : graph[i]) {
                if (e.isrev) continue;
                auto& rev_e = graph[e.to][e.rev];
                cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
            }
        }
    }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    LL N, M;
    cin >> N >> M;
    vector<vector<bool>> maps;
    maps.resize(M, vector<bool>(N, true));
    LL bl = 0, wh = 0;
    for (LL y = 0; y < N; y++) {
        string S;
        cin >> S;
        for (LL x = 0; x < M; x++) {
            if (S[x] == '.')maps[x][y] = false;
            else {
                if ((x + y) & 1)bl++;
                else wh++;
            }
        }
    }
    Dinic<LL> D(M * N + 2);
    LL vx[4] = { 0,1,0,-1 };
    LL vy[4] = { 1,0,-1,0 };
    for (LL x = 0; x < M; x++) {
        for (LL y = 0; y < N; y++) {
            if ((x + y) & 1)D.add_edge(x + y * M, M * N + 1, 1);
            else D.add_edge(M * N, x + y * M, 1);
            if (!maps[x][y])continue;
            for (LL v = 0; v < 4; v++) {
                LL nx = x + vx[v];
                LL ny = y + vy[v];
                if (nx < 0 || nx >= M || ny < 0 || ny >= N)continue;
                if (!maps[nx][ny])continue;
                if ((x + y) & 1)D.add_edge(nx + ny * M, x + y * M, 1);
                else D.add_edge(x + y * M, nx + ny * M, 1);
            }
        }
    }
    LL flow = D.max_flow(M * N, M * N + 1);
    bl -= flow;
    wh -= flow;
    LL ans = min(bl, wh);
    bl -= ans;
    wh -= ans;
    ans *= 10;
    ans += bl + wh;
    ans += flow * 100;
    cout << ans << "\n";
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0