結果

問題 No.2238 Rock and Hole
コンテスト
ユーザー otamay6
提出日時 2023-03-03 23:13:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,067 bytes
コンパイル時間 2,678 ms
コンパイル使用メモリ 213,588 KB
最終ジャッジ日時 2025-02-11 04:24:16
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

template <class T>
struct Edge {
    int rev, from, to;  // rev:逆向きの辺の番号
    T cap, original_cap;
    Edge(int r, int f, int t, T c) : rev(r), from(f), to(t), cap(c), original_cap(c) {}
};
template <class T>
struct Graph {
    vector<vector<Edge<T>>> G;
    Graph(int n = 0) : G(n) {}
    vector<Edge<T>>& operator[](int i) { return G[i]; }
    const size_t size() const { return G.size(); }
    Edge<T>& redge(Edge<T> e) {  // 逆向きの辺を返す
        return G[e.to][e.rev];   // 自己ループはないと仮定（あれば G[e.to][e.rev + 1] とする必要がある）
    }
    void add_edge(int from, int to, T cap) {  // 有向辺を加える
        G[from].push_back(Edge<T>((int)G[to].size(), from, to, cap));
        G[to].push_back(Edge<T>((int)G[from].size() - 1, to, from, 0));
    }
};
/* FordFulkerson: Ford-Fulkersonのアルゴリズムで最大流を求める構造体
    max_flow(G,s,t) ：グラフGの最大流が求まる
    副作用：G は最大流の残余ネットワークになる
    計算量: O(|f*||E|) (f*:最大流) 
*/
template <class T>
struct FordFulkerson {
    const T INF = 1e9;
    vector<int> used;
    FordFulkerson(){};
    T dfs(Graph<T>& G, int v, int t, T f) {  // 増加可能経路を見つけて増加分のフローを返す
        if (v == t) return f;
        used[v] = true;
        for (auto& e : G[v]) {
            if (!used[e.to] && e.cap > 0) {
                T d = dfs(G, e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G.redge(e).cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    T max_flow(Graph<T>& G, int s, int t) {
        T flow = 0;
        while (true) {
            used.assign(G.size(), 0);
            T f = dfs(G, s, t, INF);  // f が増加分のフロー
            if (f == 0) {
                return flow;
            } else {
                flow += f;
            }
        }
        return 0;
    }
};
int main() {
    int h,w;
    cin>>h>>w;
    assert(h*w <= 100000);
    vector<string> s(h);
    REP(i,h) cin>>s[i];
    // 岩と穴に番号を付ける

    int X = 0, Y = 0, E;
    map<pair<int,int>, int> x, yw, yh;
    REP(i, h) REP(j, w) {
        if(s[i][j] == 'r'){
            x[pair<int,int>(i,j)] = X;
            X += 1;
        }
        if(s[i][j] == 'h') {
            yw[pair<int,int>(j, i)] = Y;
            yh[pair<int,int>(i, j)] = Y;
            Y += 1;
        }
    }
    Graph<int> G(X + Y + 2);
    for (int i = 0; i < X; i++) {  // ソース(0)から X(1~X) への辺
        G.add_edge(0, i + 1, 1);
    }
     for (auto kvp: x) {  // X(1~X) から Y(X+1~X+Y) への辺
        pair<int,int> pos = kvp.first;
        int node = kvp.second;
        auto iter = yw.lower_bound(pair<int,int>(pos.second, pos.first));
        if(iter != yw.end() && iter->first.first == pos.second) {
            G.add_edge(node + 1, iter->second + X + 1, 1);
        }
        if(iter != yw.begin()) {
            iter = prev(iter);
            if(iter->first.first == pos.second) {
                G.add_edge(node + 1, iter->second + X + 1, 1);
            }
        }
        iter = yh.lower_bound(pos);
        if(iter != yh.end() && iter->first.first == pos.first) {
            G.add_edge(node + 1, iter->second + X + 1, 1);
        }
        if(iter != yh.begin()) {
            iter = prev(iter);
            if(iter->first.first == pos.first) {
                G.add_edge(node + 1, iter->second + X + 1, 1);
            }
        }
    }
    for (int i = 0; i < Y; i++) {  // Y(X+1~X+Y) からシンク(X+Y+1)への辺
        G.add_edge(i + X + 1, X + Y + 1, 1);
    }
    FordFulkerson<int> ff;
    cout << (ff.max_flow(G, 0, X + Y + 1) == X?"Yes":"No") << endl;
}
0