tkdsheep-solution-0054

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

经典题目，求起点1到终点ｎ的“不相交最短路”条数，题意实际上是求一个最小割，等价于最大流
首先分别从起点和终点开始各做一次单源最短路，这样可以找出哪些边是1到ｎ的最短路上的边
然后对于这些边，做网络流，源点是1,汇点是ｎ，每条最短路上的边流量为1,其余边流量为0,最大流即为答案
这题不用拆点的，直接边的流量为1就行，但是要注意如果有重边，则要把重边合并为1条流量为1的边
类似的题目是zoj2760

经典题目，求起点1到终点ｎ的“不相交最短路”条数，题意实际上是求一个最小割，等价于最大流

首先分别从起点和终点开始各做一次单源最短路，这样可以找出哪些边是1到ｎ的最短路上的边

然后对于这些边，做网络流，源点是1,汇点是ｎ，每条最短路上的边流量为1,其余边流量为0,最大流即为答案

这题不用拆点的，直接边的流量为1就行，但是要注意如果有重边，则要把重边合并为1条流量为1的边

类似的题目是zoj2760