题目分析

本题要求寻找从寝室（节点1）到学校（节点N）的最长周期晨跑计划，满足：

1. 周期内每天的路线在十字路口（除起点1和终点N外）不相交；
2. 在周期天数最长的前提下，总路程最短。

核心挑战是限制路径在中间节点不重叠，并同时优化“最长天数”和“最短总路程”两个目标。

算法思路

本题可通过最小费用最大流（MCMF） 模型求解，关键是利用“拆点”技巧处理节点不相交的限制：

1. 节点拆分：
   为避免中间节点（2到N-1）被多条路径重复使用，将每个中间节点i拆分为“入点”in[i]和“出点”out[i]，并在in[i]与out[i]之间连一条容量为1、费用为0的边。这条边的容量限制了节点i最多被1条路径使用（保证不相交）。
   起点1和终点N无需拆分限制（题目允许它们被所有路径共用），直接用原节点作为“出点”和“入点”。

2. 流网络构建：

   • 对于每条街道(a, b, c)（从a到b，长度c），在流网络中添加一条从out[a]到in[b]的边，容量为1（每条街道只能用一次），费用为c（路径长度）。
   • 源点设为起点1的“出点”，汇点设为终点N的“入点”。

3. 求解目标：
   最大流（max flow）对应最长周期的天数（最多的不相交路径数）；在最大流前提下，最小费用（min cost）对应总路程最短。通过MCMF算法可同时求得这两个目标。

复杂度分析

• 时间复杂度：主要取决于MCMF算法的效率。采用SPFA寻找增广路时，每次迭代复杂度为O(M)，增广次数最多为中间节点数（O(N)），因此总复杂度约为O(N*M)，可满足N≤200、M≤2×10^4的数据范围。
• 空间复杂度：O(N + M)，用于存储流网络的边和节点信息。

算法标签

• 最小费用最大流（MCMF）
• 网络流
• 拆点法（节点容量限制）
• 图论建模