题意简化

$n$ 个点的有向无环图，$k$ 个人同时从点 $1$ 出发到点 $n$。

• 每时刻每人必须走一条边（除非已到 $n$）
• 每条边每时刻只能有一个人经过
• 求最晚到达 $n$ 的人的最早可能时间

$n \le 100$, $m,k \le 1000$。

核心思想：时间分层 + 网络流

1. 问题转化

将时间离散化，构建分层图：

• 第 $i$ 层表示时间 $i$ 时的状态
• 节点 $(v, t)$ 表示在时间 $t$ 位于节点 $v$

2. 分层图建边

代码中的建图方式：

lianbian1()：初始建图

for(i=1; i<n; i++) {
    add(n+(i-1)*n, n+i*n, INF);  // 在n点可以停留
    for(j=1; j<=m; j++) {
        int f1=bian[j][0], f2=bian[j][1];
        add(f1+(i-1)*n, f2+i*n, 1);  // 从上层f1到下层f2，容量1
    }
}

• 每层有 $n$ 个节点：节点v + 层数*n
• 边容量为1：每条边每时刻只能过1人
• 点 $n$ 有无限容量边：到达后可以停留

lianbian2(ce)：动态加层

void lianbian2(int ce) {
    t = ce*n;  // 更新汇点
    add(n+(ce-1)*n, n+ce*n, INF);
    for(j=1; j<=m; j++) {
        int f1=bian[j][0], f2=bian[j][1];
        add(f1+(ce-1)*n, f2+ce*n, 1);
    }
}

动态增加时间层，直到能运送 $k$ 个人。

3. 网络流模型

• 源点：$(1,0)$（第0层的点1）
• 汇点：$(n,T)$（第T层的点n）
• 流量：$k$ 个人

每次增加时间层 $T$，检查最大流是否 $\ge k$。

4. 算法流程

1. 检查可行性：

   • 先建足够多的层（代码用 $n$ 层）
   • 跑最大流，如果 $\ge k$ 则可行

2. 二分时间（实际是枚举）：

   • 从 $T=1$ 开始，逐层增加
   • 每加一层，跑最大流
   • 当流量 $\ge k$ 时，$T$ 即为答案

关键点

1. 为什么这样建模正确？

• 每层边容量1保证每条边每时刻至多1人
• 点 $n$ 的INF边允许到达后停留
• 其他点没有停留边，因为不能在路上停留

2. 复杂度优化

• 逐层增加，避免建过大图
• 当前弧优化加速Dinic
• 每层只加新增的边

3. 可行性判断

如果最大流 $< k$，说明无论如何 $k$ 个人无法全部到达 $n$，输出 $-1$。

样例解释

输入：

8 11 3
1 2
1 3
1 4
6 7
2 5
3 6
3 2
4 6
5 7
7 8
2 7

建分层图，计算时间 $T=5$ 时最大流 $\ge 3$。

输出：5

算法步骤

1. 输入建边

2. 检查可行性：

   • 建 $n$ 层图（最长路径不超过 $n-1$）
   • 跑最大流，如果 $<k$ 输出 $-1$

3. 求解最小时间：

   • 清空图
   • 从 $T=1$ 开始循环
   • 每轮添加新的一层
   • 跑最大流
   • 当流量 $\ge k$ 时输出 $T-1$

复杂度分析

• 每层：$O(m)$ 条边
• 最大 $T$ 不超过 $n+k$（最坏情况）
• Dinic复杂度：$O(E\sqrt{V})$ 或 $O(VE)$
• 总复杂度可过 $n=100$, $m,k=1000$

代码特点

• 动态加层优化
• Dinic最大流模板
• 当前弧优化
• 可行性预判

注意点

• 输出 $i-1$ 因为循环从1开始，且检查的是能否在时间 $i$ 内完成
• 重边不影响（每条边容量独立）
• DAG保证无环，分层图也无环