AOJ2168：Luigi's Tavern

問題. Luigi's Tavern

人の勇者， 人の戦士， 人の聖職者と 人の魔術師がいる．次を満たすパーティを最大いくつ作ることができるかを求めよ．ただし，友達の制約は入力として与えられる．
　・どのパーティにも勇者がいる
　・パーティ内の勇者と戦士は友達
　・パーティ内の戦士と聖職者は友達
　・パーティ内の聖職者と魔術師は友達
　・戦士，聖職者または魔術師がいないパーティ数がそれぞれ 以下
　・聖職者がいないパーティには必ず戦士と魔術師がいる

制約：

解法. 最大流問題

次の図のようにネットワークを構成して最大流問題に帰着します．青色，緑色，オレンジ色と赤色の四角はそれぞれ勇者，戦士，聖職者と魔術師を表しています．矢印は弧を表し各弧の容量は 以外すべて1です．また，色の付いた矢印は友達同士を結ぶ弧です．このとき - 最大流が求める答えとなります．
気持ちとしては，２つの役職でのパーティへの割り当てを二部グラフの最大マッチングとして解くということを，多段的に行っていくという感じです．また，◯◯という役職がいないパーティというのは，「◯◯という役職がいない」という人を仮想的に選ぶということに対応しています．なので，四角をそれぞれ 個ずつ設置することもできますが，最大流問題では1つの頂点に置き換えることができ，また，そのようにすることで計算時間が短くなります．

計算時間： 　，

ソースコードを表示

#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;
    const Weight INF;

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

    void add_edge(const int src, const int dst, const Weight cap) {
        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 H, W, C, M, NW, NC, NM;
    while (cin >> H >> W >> C >> M >> NW >> NC >> NM, H != -1) {
        const int n = 7 + 2 * (H + W + C + M), s = 0, t = 1;
        Dinic<int> g(n);

        // ネットワークは下の層から，s -> M(Nm) -> C(Nc) -> W(Nw) -> H -> t

        // s -> M
        for (int i = 0; i < M; ++i)
            g.add_edge(0, i + 7, 1);
        // H -> t
        for (int i = 0; i < H; ++i)
            g.add_edge(i + 7 + 2 * (M + C + W) + H, 1, 1);

        // M
        for (int i = 0; i < M; ++i)
            g.add_edge(i + 7, i + 7 + M, 1);
        // C
        for (int i = 0; i < C; ++i)
            g.add_edge(i + 7 + 2 * M, i + 7 + 2 * M + C, 1);
        // W
        for (int i = 0; i < W; ++i)
            g.add_edge(i + 7 + 2 * (M + C), i + 7 + 2 * (M + C) + W, 1);
        // H
        for (int i = 0; i < H; ++i)
            g.add_edge(i + 7 + 2 * (M + C + W), i + 7 + 2 * (M + C + W) + H, 1);

        // Nm
        g.add_edge(0, 2, NM);
        for (int i = 0; i < C; ++i)
            g.add_edge(2, i + 7 + 2 * M, 1);
        // Nc
        g.add_edge(3, 4, NC);
        for (int i = 0; i < M; ++i)
            g.add_edge(i + 7 + M, 3, 1);
        for (int i = 0; i < W; ++i)
            g.add_edge(4, i + 7 + 2 * (M + C), 1);
        // Nw
        g.add_edge(5, 6, NW);
        for (int i = 0; i < C; ++i)
            g.add_edge(i + 7 + 2 * M + C, 5, 1);
        for (int i = 0; i < H; ++i)
            g.add_edge(6, i + 7 + 2 * (M + C + W), 1);

        // W -> H
        for (int i = 0, deg, dst; i < W; ++i) {
            cin >> deg;
            while (deg--) {
                cin >> dst;
                g.add_edge(i + 7 + 2 * (M + C) + W, (dst - 1) + 7 + 2 * (M + C + W), 1);
            }
        }
        // C -> W
        for (int i = 0, deg, dst; i < C; ++i) {
            cin >> deg;
            while (deg--) {
                cin >> dst;
                g.add_edge(i + 7 + 2 * M + C, (dst - 1) + 7 + 2 * (M + C), 1);
            }
        }
        // M -> C
        for (int i = 0, deg, dst; i < M; ++i) {
            cin >> deg;
            while (deg--) {
                cin >> dst;
                g.add_edge(i + 7 + M, (dst - 1) + 7 + 2 * M, 1);
            }
        }

        cout << g.MaximumFlow(s, t) << '\n';
    }

    return 0;
}

巨人の肩の上に立つような問題