p8857 sol（POI2002 滑雪者）

· · 题解

考虑到要选中若干条从起点到终点的路径以覆盖整张 DAG，考虑用网络流刻画。

令起点为虚拟源点，终点为虚拟汇点。对于原图一条边 (u,v)，由于其至少要被覆盖一次，所以它的流量必须在 [1,+\infty) 之间。我们需要求出这张网络的最小流。

按照有源汇上下界网络流的套路解决这张图的一个可行流，并将所有正向边（除去虚拟汇点向虚拟源点的边，真实源点向所有点的边，以及所有点向真实汇点的边）的流量加到答案中。这表示一种可行覆盖方案的花费次数。

接下来，寻找虚拟汇点向虚拟源点的增广路，这可以理解为增广路上的流量被撤销了。这等价于寻找虚拟汇点向虚拟源点的最大流。最大流的值表示至多能撤销多少条路径，拿答案减去其就行了。