Multiple Source Multiple Sink Max flow - 多源点多汇点最大流

求网络流 $G = <V,E>$ 的最大流， $G$ 是多源点、多汇点，边的容量都为正整数的网络。

将多源点、多汇点的网络改造为单源点、单汇点的，就可以将该问题转化为普通的最大流问题。

设 $n$ 个源点为 $[s_1, s_2, \dots, s_n]$ ， $m$ 个汇点为 $[t_1, t_2, \dots, t_m]$ ，如下图所示：

新增源点 $s$ 和汇点 $t$ ，构造新增源点 $s$ 到所有源点 $s_1, s_2, \dots, s_n$ 的边，容量为无穷大，即

$c(s, s_i) = + \infty$

其中 $1 \leq i \leq n$ 。

构造所有汇点 $t_1, t_2, \dots, t_m$ 到新增汇点 $t$ 的边，容量为无穷大，即

$c(t_i, t) = + \infty$

其中 $1 \leq i \leq m$ 。

把原网络中的源点汇点当作普通节点，即可得到新的单源点、单汇点网络，如下图所示：

新网络的最大流即为原网络的最大流，该算法的时间复杂度与所采用最大流算法的时间复杂度相同。