2014-team4/code/network-flow

从 Trac 迁移的文章

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

原文章内容如下：

参考资料： 《一种简易的方法求解流量有上下界的网络中网络流问题》 by 周源

一些定义：

   (i,j,high,low)表示i到j，上界为high，下界为low的一条边。

建图方法：

1. 无源汇可行流（最大流）

       1)设超级源S，超级汇T

       2)对于每条边(i,j,high,low): 新增(S,j,low,0)和(i,T,low,0)。原图中的边变为(i,j,high-low,0)

       3)跑一遍最大流，如果连接S和T的边满流，则存在可行流。

2. 有源汇可行流（最大流）

       1)设超级源S，超级汇T，原源s,原汇t

       2)新增边(t,s,inf,0)，转化为无源汇。按无源汇连边。

       3)跑一遍最大流，如果连接S和T的边满流，则存在可行流。

to be continued...

参考资料： 《一种简易的方法求解流量有上下界的网络中网络流问题》 by 周源

一些定义：

(i,j,high,low)表示i到j，上界为high，下界为low的一条边。

建图方法：

1. 无源汇可行流（最大流）

1)设超级源S，超级汇T

2)对于每条边(i,j,high,low): 新增(S,j,low,0)和(i,T,low,0)。原图中的边变为(i,j,high-low,0)

3)跑一遍最大流，如果连接S和T的边满流，则存在可行流。

2. 有源汇可行流（最大流）

1)设超级源S，超级汇T，原源s,原汇t

2)新增边(t,s,inf,0)，转化为无源汇。按无源汇连边。

3)跑一遍最大流，如果连接S和T的边满流，则存在可行流。

to be continued...