题目解析

限制每条边只能选一次,很容易理解(实现),如何限制每个点只能选一次呢: 拆点成边

在本文上如何限制只能跑固定的点的数量呢: 通过路径(管道)联通性限制:

• dp[i] == 1 的点作为起点: 连接源点
• dp[i] == S 的点作为终点: 连接汇点

反证法证明:

• 如果 dp[j] == s, 那么对应j的的起点 i 的dp值 一定是 $dp[i] = 1$

反证法证明: 最大流一定就是选的长度为S的lis的数量(不漏)

代码