CSES 2130：Distinct Routes II

CSES 2130：Distinct Routes II

題目大意：有 $n$ 個房間，$m$ 個傳送門連接兩個房間，規定在一天要從房間 $1$ 走到房間 $n$，要走 $k$ 天，且一個傳送門只能用一次，用一次要花一塊，問能不能達成，若可以，最少要花幾元？

解法：$\text{MCMF}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct Edge {
    int a, b, cap, cost;
};

int n, m, k;

struct Min_Cost_Max_Flow {
    vector<vector<int>> adj;
    vector<Edge> edge;
    vector<int> dis, pre;
    Min_Cost_Max_Flow() {
        adj.resize (n + 1);
        edge.resize (2 * m);
        dis.resize (n + 1);
        pre.resize (n + 1);
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back (2 * i);
            adj[b].push_back (2 * i + 1);
            edge[2 * i] = {a, b, 1, 1};
            edge[2 * i + 1] = {b, a, 0, -1};
        }
    }
    void spfa() {
        bool inq[n + 1] = {};
        fill (dis.begin(), dis.end(), INF);
        fill (pre.begin(), pre.end(), 0);
        queue<int> q;
        dis[1] = 0;
        q.push (1);
        while (!q.empty()) {
            int pos = q.front();
            q.pop();
            inq[pos] = 0;
            for (int id : adj[pos]) {
                Edge e = edge[id];
                if (e.cap > 0 && dis[pos] + e.cost < dis[e.b]) {
                    dis[e.b] = dis[pos] + e.cost;
                    pre[e.b] = id;
                    if (!inq[e.b]) {
                        inq[e.b] = 1;
                        q.push (e.b);
                    }
                }
            }
        }
    }
    int get_flow() {
        int flow = 0, cost = 0;
        while (flow < k) {
            spfa();
            if (dis[n] == INF)
                break;
            int f = k - flow, pos = n;
            while (pos != 1) {
                int id = pre[pos];
                f = min (f, edge[id].cap);
                pos = edge[id].a;
            }
            flow += f;
            cost += dis[n] * f;
            pos = n;
            while (pos != 1) {
                int id = pre[pos];
                edge[id].cap -= f;
                edge[id ^ 1].cap += f;
                pos = edge[id].a;
            }
        }
        return flow < k ? -1 : cost;
    }
    void get_ans() {
        int cost;
        cout << (cost = get_flow()) << '\n';
        if (cost == -1)
            return;
        bool vs[2 * m] = {};
        while (k--) {
            vector<int> v;
            v.push_back (1);
            while (v.back() != n) {
                int pos = v.back();
                for (int id : adj[pos]) {
                    Edge e = edge[id];
                    if (id % 2 || vs[id] || e.cap != 0)
                        continue;
                    vs[id] = 1;
                    v.push_back (e.b);
                    break;
                }
            }
            cout << v.size() << '\n';
            for (int x : v)
                cout << x << ' ';
            cout << '\n';
        }
    }
} mcmf;

void solve() {
    cin >> n >> m >> k;
    mcmf = Min_Cost_Max_Flow();
    mcmf.get_ans();
}

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

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！