結果

問題 No.421 しろくろチョコレート
ユーザー MitI_7
提出日時 2016-10-03 22:39:54
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 202 ms / 2,000 ms
コード長 4,236 bytes
コンパイル時間 1,324 ms
コンパイル使用メモリ 107,232 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:10:09
合計ジャッジ時間 4,030 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <fstream>
#include <bitset>
#include <time.h>
#include <assert.h>
#define LL long long
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define SZ(x) ((int)(x).size())
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define AND &&
#define OR ||
#define NOT !
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define EPS 1e-14
template<typename T> inline void DUMP(T x) { std::cerr << x << std::endl; }
template<typename T> inline void DUMP_V(std::vector<T> v) { for (unsigned int i = 0; i < v.size(); ++i) { std::cerr << v[i] << ((i == v.size() - 1) ? 
    "n" : " "); } }
template<typename T> inline void DUMP_V2(std::vector<std::vector<T>> v) { for (unsigned int i = 0; i < v.size(); ++i) { for (unsigned int j = 0; j < 
    v[i].size(); ++j) { std::cerr << v[i][j] << " "; } std::cerr << std::endl; } }
using namespace std;
class FordFulkerson {
private:
    struct Edge { int to; int capacity; int rev; }; // 辺(行き先、容量、逆辺のidx(Graph[to][rev]でアクセス))
    map<int, vector<Edge>> Graph;                   // グラフ(ノード番号: {辺1, 辺2, ...})
    // fromからtoまでの増加パスをDFSで探す
    int dfs(int from, int sink, int flow, set<int> &used) {
        if (from == sink) return flow;
        used.insert(from);
        for (Edge &e : Graph[from]) {
            if (used.find(e.to) == used.end() && e.capacity > 0) {
                int d = dfs(e.to, sink, min(flow, e.capacity), used);
                // 流せる
                if (d > 0) {
                    e.capacity -= d;
                    Graph[e.to][e.rev].capacity += d;
                    return d;
                }
            }
        }
        // fromからtoへのパスがみつからない
        return 0;
    }
public:
    // グラフに辺を追加
    void addEdge(int from, int to, int capacity) {
        Graph[from].push_back({ to, capacity, (int)Graph[to].size() });
        Graph[to].push_back({ from, 0, (int)Graph[from].size() - 1 });
    }
    // sourceからsinkへの最大流を求める
    // O(F|E|) Fは最大の流量
    int maxFlow(int source, int sink) {
        int flow = 0;
        while (true) {
            set<int> used;
            int f = dfs(source, sink, INT_MAX, used);
            if (f == 0) { break; };
            flow += f;
        }
        return flow;
    }
};
// 4近傍（右, 下, 左, 上）
vector<int> dy = { 0, -1, 0, 1 };
vector<int> dx = { 1, 0, -1, 0 };
bool inside(int y, int x, int H, int W) {
    return 0 <= y && y < H && 0 <= x && x < W;
}
int main(int argc, char *argv[]) {
    FordFulkerson ff;
    
    int n, m;
    string s;
    vector<string> v;
    cin >> n >> m;
    FOR(i, 0, n) {
        cin >> s;
        v.push_back(s);
    }
    int source = n * m + 1;
    int sink = n * m + 2;
    int w = 0;
    int b = 0;
    FOR(y, 0, n) {
        FOR(x, 0, m) {
            int node = y * m + x;
            if (v[y][x] == 'w') {
                w++;
                ff.addEdge(source, node, 1);
                for (int i = 0; i < dy.size(); i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];
                    if (inside(ny, nx, n, m)) {
                        if (v[ny][nx] == 'b') {
                            int black = ny * m + nx;
                            ff.addEdge(node, black, 1);
                        }
                    }
                }
                
            }
            else if (v[y][x] == 'b') {
                b++;
                ff.addEdge(node, sink, 1);
            }
            
        }
    }
    int ans = 0;
    int p = ff.maxFlow(source, sink);
    
    ans += p * 100;
    w -= p;
    b -= p;
    int t = min(w, b);
    ans += t * 10;
    
    ans += max(w, b) - t;
    
    cout << ans << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0