题解#4

这是一道经典的有向无环图（$DAG$）上的多源点汇点流/时间扩展问题。
问题分析
我们需要找到$k$个人从节点 1 到节点$n$的最晚到达时间的最小值。每个人必须沿着边走，且每条边每个时刻只能有一个人经过。
由于图是$DAG$，且边的容量为 1（每个时刻），这实际上是一个最小费用最大流问题，或者是二分图匹配问题。
我们可以将问题转化为：

每个人必须从1到$n$。

每条边 ($u,v$) 在每个时刻$t$只能被一个人占用。

求所有人到达$n$的最大时间的最小值。
关键观察
1.
$DAG$上的路径：每个人从1到$n$的路径长度（边数）是固定的，但具体路径可以不同。
2.
边的容量：每条边每个时刻只能被一个人使用。这意味着如果两个人同时到达某个节点，他们不能同时通过同一条出边。
3.
时间扩展：我们可以将每个节点$v$复制成多个时间点($v, t$)，表示在时刻$t$位于节点$v$。边 ($u,v$) 在时间 $t$被使用，对应从 ($u, t$) 到 ($v, t+1$) 的边。

代码：

#include <bits/stdc++.h>
using namespace std;

struct Dinic {
    struct Edge {
        int to, cap, rev;
    };
    vector<vector<Edge>> g;
    vector<int> level, iter;
    int n;
    
    void init(int n_) {
        n = n_;
        g.assign(n, {});
        level.resize(n);
        iter.resize(n);
    }
    
    void add_edge(int from, int to, int cap) {
        g[from].push_back({to, cap, (int)g[to].size()});
        g[to].push_back({from, 0, (int)g[from].size() - 1});
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto &e : g[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }
    
    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    int max_flow(int s, int t) {
        int flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            int f;
            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
};

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    
    vector<pair<int,int>> edges(m);
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        edges[i] = {u, v};
        adj[u].push_back(v);
    }
    
    // 计算每个节点到 n 的最长路径（DAG 上）
    vector<int> d(n + 1, -1);
    // 拓扑排序
    vector<int> indeg(n + 1, 0);
    for (auto &[u, v] : edges) indeg[v]++;
    queue<int> q;
    for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.push(i);
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    // 反向计算最长距离
    d[n] = 0;
    for (int i = n - 1; i >= 1; i--) {
        int u = topo[i - 1]; // 假设 topo 包含 1..n
        // 实际上需要按逆拓扑序处理
    }
    // 更简单的做法：按逆拓扑序
    for (int i = (int)topo.size() - 1; i >= 0; i--) {
        int u = topo[i];
        if (u == n) { d[u] = 0; continue; }
        int mx = -1;
        for (int v : adj[u]) {
            if (d[v] >= 0) mx = max(mx, d[v] + 1);
        }
        d[u] = mx;
    }
    
    if (d[1] < 0) {
        printf("-1\n");
        return 0;
    }
    
    int lo = d[1], hi = d[1] + k - 1;
    int ans = -1;
    
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        // 建图：节点 (v, t) 编号为 (t-1)*n + v，0 表示源点，mid*n+1 表示汇点
        // 总节点数：n*(mid+1) + 2
        int T = mid;
        int nodes = n * (T + 1) + 2;
        int S = 0, TT = nodes - 1;
        Dinic dinic;
        dinic.init(nodes);
        
        // 源点到 (1, 0)
        dinic.add_edge(S, 1, k); // (1,0) 的编号是 1
        
        // 时间扩展边
        for (int t = 0; t < T; t++) {
            for (auto &[u, v] : edges) {
                int from = t * n + u;
                int to = (t + 1) * n + v;
                dinic.add_edge(from, to, 1);
            }
            // 等待边
            for (int v = 1; v <= n; v++) {
                int from = t * n + v;
                int to = (t + 1) * n + v;
                dinic.add_edge(from, to, k);
            }
        }
        
        // (n, t) 到汇点
        for (int t = 0; t <= T; t++) {
            int from = t * n + n;
            dinic.add_edge(from, TT, k);
        }
        
        if (dinic.max_flow(S, TT) >= k) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    
    printf("%d\n", ans);
    return 0;
}