题目分析

这是一个分层图网络流问题：$T$ 个人要从城市 $1$ 到城市 $N$，每条航线每天有票数限制，求最后一人到达的最早时间。

算法思路：逐天扩展 + 最大流

核心思想

• 将时间按天分层，每天对应一层节点
• 逐天扩展网络流图，直到累计流量达到 $T$
• 最后扩展的天数即为答案

网络流建模

节点编号

• 源点：$1$
• 汇点：$2$
• 第 $t$ 天城市 $i$：$n \cdot t + i + 2$

边构造

1. 源点到第1天起点：

   add(1, 3, k);  // 1→第0天城市1(3)，容量k
   

2. 每天终点到汇点：

   add(n*t+n+2, 2, INF);  // 第t天城市N→汇点
   

3. 城市停留边：

   add(n*(t-1)+i+2, n*t+i+2, INF);  // 城市i停留一天
   

4. 航班边：

   add(n*(t-1)+u+2, n*t+v+2, w);  // 第t天航班u→v
   

算法流程

for(int t=1, sum=0; ; t++) {
    // 添加第t层节点和边
    add(n*t+n+2, 2, INF);  // 新层终点到汇点
    
    for(int i=1; i<=n; i++) 
        add(旧层i, 新层i, INF);  // 停留边
        
    for(int i=1; i<=m; i++)
        add(旧层u[i], 新层v[i], w[i]);  // 航班边
        
    sum += dinic(1, 2, n*t+n+2, e, head);  // 累计流量
    
    if(sum == k) return cout << t, 0;  // 所有人到达
}

网络流算法

使用 Dinic 算法求最大流：

• BFS 分层
• DFS 多路增广
• 当前弧优化

复杂度分析

• 每天扩展：$O(n+m)$ 条边
• Dinic 复杂度：$O(E\sqrt{V})$
• 总复杂度：$O(D \cdot (n+m)^{1.5})$，$D$ 为答案天数

在 $n \leq 50, m \leq 2450, T \leq 50$ 时可行。

样例验证

输入：

3 3 5
1 2 1
2 3 5  
3 1 4

处理过程：

• 第 $1$ 天：$1$ 人到城市 $2$
• 第 $2-6$ 天：逐步运送剩余人员
• 第 $6$ 天：$5$ 人全部到达

输出：6，与样例一致。

算法优势

• 动态建图：避免预先估计天数
• 保证最优：找到最早可能时间
• 高效可行：数据范围内运行良好

该解法通过分层网络流精确建模了带容量限制的多日运输问题。