九州大学プログラミングコンテスト2014 H問題：お風呂は気持ちいい

問題. お風呂は気持ちいい

人の魔法使いがいて，その内 人が魔導石に近い場所にいる．魔法使い から魔法使い へ最大 の魔力を受け渡すことができるという 個のリストが与えられる．魔導石からは無限に魔力が湧き出ており，魔導石に近い魔法使いは魔導石から無制限に魔力を得ることができる．魔法使いの1人であるアスナへ 以上の魔力を渡すことができるかを判定せよ．

制約： ，，，

解法. 最大流問題

魔導石と各魔法使いを頂点として，魔導石から魔導石に近い魔法使いへ容量が無限大の弧を張る．また，魔力の受け渡しの制約として魔法使い から魔法使い へ容量 の弧を張る．このとき，魔導石からアスナへの最大流が 以上ならば答えを Yes ，それ以外ならば No と出力する．

計算時間： 　

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

template<typename Weight>
struct Dinic {
    struct Edge {
        int src, dst, rev;
        Weight weight;
        Edge(int f, int t, Weight cap, int rev = 0) :
            src(f), dst(t), rev(rev), weight(cap) {}
    };

    int n;
    vector<vector<Edge>> adj;
    static const Weight INF = numeric_limits<Weight>::max();

    Dinic(int _n) : n(_n), adj(n) {}
    // Dinic(int _n) : n(_n), adj(n), INF(numeric_limits<Weight>::max()) {}

    void add_edge(const int src, const int dst, const Weight cap = INF) {
        adj[src].emplace_back(Edge(src, dst, cap, adj[dst].size()));
        adj[dst].emplace_back(Edge(dst, src, 0, adj[src].size() - 1));
    }

    Weight MaximumFlow(const int s, const int t) {
        Weight flow = 0;
        while(true) {
            vector<int> level(n, -1), iter(n);
            Bfs(s, level);
            if(level[t] == -1) break;
            for (Weight f = 0; (f = Dfs(s, t, INF, level, iter)) > 0; )
                flow += f;
        }
        return flow;
    }

    void Bfs(const int s, vector<int> &level){
        queue<int> que;
        for (level[s] = 0, que.push(s); !que.empty(); ) {
            const int v = que.front(); que.pop();
            for (auto &e : adj[v])
                if(0 < e.weight && level[e.dst] == -1){
                    level[e.dst] = level[v] + 1;
                    que.push(e.dst);
                }
        }
    }

    Weight Dfs(int v, int t, Weight flow, vector<int> &level, vector<int> &iter) {
        if(v == t) return flow;
        for ( ; iter[v] < (int)adj[v].size(); ++iter[v]) {
            Edge &e = adj[v][iter[v]];

            if(0 < e.weight && level[v] < level[e.dst]){
                Weight d = Dfs(e.dst, t, min(flow, e.weight), level, iter);
                if(0 < d){
                    e.weight -= d;
                    adj[e.dst][e.rev].weight += d;
                    return d;
                }
            }
        }
        return 0;
    }
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, m, p, g;
    cin >> n >> m >> p >> g;

    const int s = m, t = 0;
    Dinic<int> graph(m + 1);
    for (int i = 0, l; i < g; ++i) {
        cin >> l;
        graph.add_edge(s, l);
    }
    for (int i = 0; i < n; ++i) {
        int from, to, cap;
        cin >> from >> to >> cap;
        graph.add_edge(from, to, cap);
    }

    cout << (p <= graph.MaximumFlow(s, t) ? "Yes" : "No") << endl;

    return 0;
}

まとめ

巨人の肩の上に立つ問題