最小費用の最大流を流すネットワークフロー問題！

問題概要

$N$ 個の駅があり、 $1, 2, \dots, N$ と番号づけられている。

駅 $i$ と駅 $i+1$ の間には $M_{i}$ 種類の電車が走っていて、 $j$ 番目の電車は

駅 $i$ を時刻 $X_{i, j}$ に出発して、
駅 $i+1$ に時刻 $Y_{i, j}$ に到着し、
料金は $C_{i, j}$ である。

今、 $G$ 人が時刻 $0$ に駅 $1$ にいて、それぞれ電車を乗り継いで駅 $N$ を目指したい。ここで、乗り継ぎにかかる時間は無視できるものとする。つまり、駅 $i$ に時刻 $t$ に到着したとしたとき、駅 $i$ を時刻 $t$ 以降に発車する電車に乗ることが可能である。

なお、厳しい制約がある。それは

「どの $2$ 人も、同じ駅に同時刻に到着してはいけない」

というものだ。異なる電車であっても、同じ駅に同時刻に到着してはいけない。

この制約条件を守りながら、 $G$ 人のうち、最大で何人が駅 $N$ に到着できるかを求めよ。また、その場合に、到着したメンバーの払った料金の総和の最小値を求めよ。

制約

$2 \le N \le 100$
$1 \le M_{i} \le 20$
$0 \le X_{i, j} \le Y_{i, j} \le 10^{6}$

考えたこと

よくある (駅, 時刻) をペアにした頂点をもつネットワーク上のフロー問題だ！！

頂点に、駅情報だけでなく、時刻情報を持たせることがポイントだ。ただし愚直にやると、時刻は $0$ から $10^{6}$ までの値がありうるので、頂点数は $10^{8}$ のオーダーになってしまう。これでは間に合わない。

そこで、

駅 $i$ になんらかの列車が到着しうる時刻
駅 $i$ からなんらかの列車が発車しうる時刻

のみを採用すればよい。これで頂点数は $O(NM)$ となる。ネットワークの大きさは現実的になる。

基本的には、このネットワーク上で、最小費用の最大流を流せばよい。つまり、最大流量を $F$ としたとき、流量 $\min(F, G)$ の最小費用流を求めればよい。

頂点流量 1 以下の制約

ここで、制約条件「どの $2$ 人も、同じ駅に同時刻に到着してはいけない」を考慮しよう。

これは言い換えれば、(駅 $i$ , 時刻 $t$ ) を表す頂点に「容量 1 以下」という制約と解釈できる。

このように、頂点に対して容量制限のあるフローでは、頂点を分裂させて、その間にその容量制限をもつ辺を張るのが定石だ。今回もそれで上手くいく。

解答例

一見すると最大流を求めてから、最小費用流を求めないといけない問題と感じてしまうが、まとめてできる。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using pll = pair<long long, long long>;

// edge class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct FlowCostEdge {
    // core members
    int rev, from, to;
    FLOWTYPE cap, icap, flow;
    COSTTYPE cost;
    
    // constructor
    FlowCostEdge(int rev, int from, int to, FLOWTYPE cap, COSTTYPE cost)
    : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(0), cost(cost) {}
    void reset() { cap = icap, flow = 0; }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowCostEdge& e) {
        return s << e.from << " -> " << e.to
        << " (" << e.flow << "/" << e.icap << ", " << e.cost << ")";
    }
};

// graph class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct FlowCostGraph {
    // core members
    vector<vector<FlowCostEdge<FLOWTYPE, COSTTYPE>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowCostGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.assign(n, FlowCostEdge<FLOWTYPE, COSTTYPE>());
        pos.clear();
    }
    
    // getter
    vector<FlowCostEdge<FLOWTYPE, COSTTYPE>> &operator [] (int i) {
        return list[i];
    }
    const vector<FlowCostEdge<FLOWTYPE, COSTTYPE>> &operator [] (int i) const {
        return list[i];
    }
    size_t size() const {
        return list.size();
    }
    FlowCostEdge<FLOWTYPE, COSTTYPE> &get_rev_edge
    (const FlowCostEdge<FLOWTYPE, COSTTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    FlowCostEdge<FLOWTYPE, COSTTYPE> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowCostEdge<FLOWTYPE, COSTTYPE> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowCostEdge<FLOWTYPE, COSTTYPE>> get_edges() const {
        vector<FlowCostEdge<FLOWTYPE, COSTTYPE>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowCostEdge<FLOWTYPE, COSTTYPE> &e : list[i]) e.reset();
        }
    }
    
    // add_edge
    void add_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost) {
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(FlowCostEdge<FLOWTYPE, COSTTYPE>
                             ((int)list[to].size(), from, to, cap, cost));
        list[to].push_back(FlowCostEdge<FLOWTYPE, COSTTYPE>
                           ((int)list[from].size() - 1, to, from, 0, -cost));
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowCostGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// min-cost max-flow (<= limit_flow), slope ver.
template<class FLOWTYPE, class COSTTYPE> vector<pair<FLOWTYPE, COSTTYPE>>
MinCostFlowSlope(FlowCostGraph<FLOWTYPE, COSTTYPE> &G, int S, int T, FLOWTYPE limit_flow)
{
    // result values
    FLOWTYPE cur_flow = 0;
    COSTTYPE cur_cost = 0, pre_cost = -1;
    vector<pair<FLOWTYPE, COSTTYPE>> res;
    res.emplace_back(cur_flow, cur_cost);
    
    // intermediate values
    vector<COSTTYPE> dual((int)G.size(), 0), dist((int)G.size());
    vector<int> prevv((int)G.size(), -1), preve((int)G.size(), -1);
    
    // dual
    auto dual_step = [&]() -> bool {
        priority_queue<pair<COSTTYPE,int>, vector<pair<COSTTYPE,int>>, greater<pair<COSTTYPE,int>>> que;
        que.push({0, S});
        dist.assign((int)G.size(), numeric_limits<COSTTYPE>::max());
        dist[S] = 0;
        while (!que.empty()) {
            auto [cur_cost, v] = que.top();
            que.pop();
            if (dist[v] < cur_cost) continue;
            for (int i = 0; i < (int)G[v].size(); ++i) {
                const auto &e = G[v][i];
                COSTTYPE new_cost = e.cost + dual[v] - dual[e.to];
                if (e.cap > 0 && dist[e.to] > dist[v] + new_cost) {
                    dist[e.to] = dist[v] + new_cost;
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push({dist[e.to], e.to});
                }
            }
        }
        if (dist[T] == numeric_limits<COSTTYPE>::max()) return false;
        for (int v = 0; v < (int)G.size(); ++v) {
            if (dist[T] == numeric_limits<COSTTYPE>::max()) continue;
            dual[v] -= dist[T] - dist[v];
        }
        return true;
    };
    
    // primal
    auto primal_step = [&]() -> void {
        FLOWTYPE flow = limit_flow - cur_flow;
        COSTTYPE cost = -dual[S];
        for (int v = T; v != S; v = prevv[v]) {
            flow = min(flow, G[prevv[v]][preve[v]].cap);
        }
        for (int v = T; v != S; v = prevv[v]) {
            FlowCostEdge<FLOWTYPE, COSTTYPE> &e = G[prevv[v]][preve[v]];
            FlowCostEdge<FLOWTYPE, COSTTYPE> &re = G.get_rev_edge(e);
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
        }
        cur_flow += flow;
        cur_cost += flow * cost;
        if (pre_cost == cost) res.pop_back();
        res.emplace_back(cur_flow, cur_cost);
        pre_cost = cur_cost;
    };
    
    // primal-dual
    while (cur_flow < limit_flow) {
        if (!dual_step()) break;
        primal_step();
    }
    return res;
}

// min-cost max-flow, slope ver.
template<class FLOWTYPE, class COSTTYPE> vector<pair<FLOWTYPE, COSTTYPE>>
MinCostFlowSlope(FlowCostGraph<FLOWTYPE, COSTTYPE> &G, int S, int T)
{
    return MinCostFlowSlope(G, S, T, numeric_limits<FLOWTYPE>::max());
}

// min-cost max-flow (<= limit_flow)
template<class FLOWTYPE, class COSTTYPE> pair<FLOWTYPE, COSTTYPE>
MinCostFlow(FlowCostGraph<FLOWTYPE, COSTTYPE> &G, int S, int T, FLOWTYPE limit_flow)
{
    return MinCostFlowSlope(G, S, T, limit_flow).back();
}

// min-cost max-flow (<= limit_flow)
template<class FLOWTYPE, class COSTTYPE> pair<FLOWTYPE, COSTTYPE>
MinCostFlow(FlowCostGraph<FLOWTYPE, COSTTYPE> &G, int S, int T)
{
    return MinCostFlow(G, S, T, numeric_limits<FLOWTYPE>::max());
}

int main() {
    int N, maxF;
    while (cin >> N, N) {
        // 入力
        vector<int> M(N-1);
        vector<vector<int>> X(N-1), Y(N-1), C(N-1);
        
        // (駅, 時刻) → 入って来る側の頂点番号
        map<pint, int> index;
        int vertex_num = 0;
        
        // 各駅の到着時刻と発車時刻
        vector<set<int>> intime(N), outtime(N);
        
        // 入力受け取り
        for (int i = 0; i < N-1; ++i) {
            cin >> M[i];
            X[i].resize(M[i]), Y[i].resize(M[i]), C[i].resize(M[i]);
            for (int j = 0; j < M[i]; ++j) {
                cin >> X[i][j] >> Y[i][j] >> C[i][j];
                outtime[i].insert(X[i][j]);
                intime[i+1].insert(Y[i][j]);
                if (!index.count(pint(i, X[i][j]))) {
                    index[pint(i, X[i][j])] = vertex_num;
                    vertex_num += 2;
                }
                if (!index.count(pint(i+1, Y[i][j]))) {
                    index[pint(i+1, Y[i][j])] = vertex_num;
                    vertex_num += 2;
                }
            }
        }
        cin >> maxF;
        
        // グラフを構築
        int source = vertex_num++, sink = vertex_num++;
        FlowCostGraph<int, int> G(vertex_num);
        const int INF = maxF;  // 理論上流せる上限

        // ソース → 最初の駅
        for (auto t : outtime[0]) {
            G.add_edge(source, index[pint(0, t)] + 1, INF, 0);
        }
        
        // 最後の駅 → シンク
        for (auto t : intime[N-1]) {
            G.add_edge(index[pint(N-1, t)] + 1, sink, INF, 0);
        }
        
        // 各駅の intime (容量 1) を分裂
        for (int i = 0; i < N; ++i) {
            for (auto t : intime[i]) {
                G.add_edge(index[pint(i, t)], index[pint(i, t)] + 1, 1, 0);
            }
        }
        
        // 各駅の intime -> outtime
        for (int i = 0; i < N; ++i) {
            for (auto t1 : intime[i]) {
                for (auto t2 : outtime[i]) {
                    if (t1 <= t2) {
                        G.add_edge(index[pint(i, t1)] + 1, index[pint(i, t2)] + 1, INF, 0);
                    }
                }
            }
        }
        
        // 各電車
        for (int i = 0; i < N-1; ++i) {
            for (int j = 0; j < X[i].size(); ++j) {
                G.add_edge(index[pint(i, X[i][j])] + 1, index[pint(i+1, Y[i][j])], 1, C[i][j]);
            }
        }

        // 最小費用最大流を流す
        auto [max_flow, min_cost] = MinCostFlow(G, source, sink, maxF);
        cout << max_flow << " " << min_cost << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1088 School Excursion

問題概要

制約

考えたこと

頂点流量 1 以下の制約

解答例