CSES 1711：Distinct Routes

CSES 1711：Distinct Routes

題目大意：有 $n$ 個點、$m$ 個有向邊，定義一天為從點 $1$ 走到點 $n$，每個邊只能走一次，問最多能走幾天。

解法：最大流跑一次，再 $dfs$ 找答案。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e9;
 
int n, m;
 
struct Edge {
    int a, b, cap, flow = 0;
    Edge() {}
    Edge (int a, int b, int cap) : a (a), b (b), cap (cap) {}
};
 
struct Dinic {
    int cnt = 0;
    vector<int> level, ptr, v;
    vector<Edge> edge;
    vector<bool> vs;
    vector<vector<int>> adj;
    queue<int> q;
 
    Dinic() {
        level.resize (n + 1);
        ptr.resize (n + 1);
        adj.resize (n + 1);
        vs.resize (2 * m + 1);
    }
 
    void add_edge (int a, int b, int cap) {
        edge.emplace_back (a, b, cap);
        edge.emplace_back (b, a, 0);
        adj[a].push_back (cnt++);
        adj[b].push_back (cnt++);
    }
 
    bool bfs() {
        while (!q.empty()) {
            int pos = q.front();
            q.pop();
            for (int id : adj[pos]) {
                int np = edge[id].b;
                if (edge[id].cap == edge[id].flow || level[np])
                    continue;
                level[np] = level[pos] + 1;
                q.push (np);
            }
        }
        return level[n] != 0;
    }
 
    int dfs (int pos, int now) {
        if (pos == n || now == 0)
            return now;
        for (int &i = ptr[pos]; i < adj[pos].size(); i++) {
            int id = adj[pos][i], np = edge[id].b;
            if (level[np] != level[pos] + 1 || edge[id].cap == edge[id].flow)
                continue;
            int mn = dfs (np, min (now, edge[id].cap - edge[id].flow));
            if (mn == 0)
                continue;
            edge[id].flow += mn;
            edge[id ^ 1].flow -= mn;
            return mn;
        }
        return 0;
    }
 
    int flow() {
        int re = 0;
        while (1) {
            fill (level.begin(), level.end(), 0);
            fill (ptr.begin(), ptr.end(), 0);
            level[1] = 1, q.push (1);
            if (!bfs())
                return re;
            while (int f = dfs (1, INF))
                re += f;
        }
    }
 
    bool dfv (int pos) {
        if (pos == n) {
            v.push_back (pos);
            return 1;
        }
        for (int id : adj[pos]) {
            int np = edge[id].b;
            if (vs[id] || id % 2 || edge[id].cap != edge[id].flow)
                continue;
            vs[id] = 1;
            if (dfv (np)) {
                edge[id].flow--;
                v.push_back (pos);
                vs[id] = 0;
                return 1;
            }
            vs[id] = 0;
        }
        return 0;
    }
 
    void ans() {
        int f = flow();
        cout << f << '\n';
        while (f--) {
            v.clear();
            dfv (1);
            cout << v.size() << '\n';
            reverse (v.begin(), v.end());
            for (int x : v)
                cout << x << ' ';
            cout << '\n';
        }
    }
} dinic;
 
void solve() {
    cin >> n >> m;
    dinic = Dinic();
    while (m--) {
        int a, b;
        cin >> a >> b;
        dinic.add_edge (a, b, 1);
    }
    dinic.ans();
}
 
int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

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