网络流-基础概念

网络

网络是一个由 \(n\) 个点 \(m\) 条边组成的有向图 \(G\)，满足每一条边 \(x\to y\) 都有边权 \(C_{x\to y}\)，我们称 \(C_{x\to y}\) 为容量。图中还有两个特别的点，分别是源点 \(S\) 和汇点 \(T\)，满足 \(S\ne T\)。

流

如果函数 \(f(x\to y)\) 满足以下的要求，那么我们称函数 \(f(x\to y)\) 为流函数。

1. 容量限制：对于任意边 \(x\to y\)，满足 \(f(x\to y)\le C_{x\to y}\)。
2. 斜对称：对于任意边 \(x\to y\)，满足 \(f(x\to y)+f(y\to x)=0\)。
3. 流量守恒：对于所有的边 \(S\to x\) 和 \(y\to T\)，满足其函数 \(f\) 的和相等。

对于任意边 \(x\to y\)，其 \(f(x\to y)\) 称为变得流量，\(C_{x\to y}-f(x\to y)\) 称为边的剩余流量。对于所有的边 \(S\to x\) 的 \(f(S\to x)\) 的和被称为这个网络的流量。定义所有的剩余流量不为 \(0\) 的边组成的网络为残量网络。

总结

通俗的理解，网络就是一个很理想的自来水供应系统，每一个管道都有自己的单位时间内的最大流量。即使在前面给出的水再多一旦超出了容量，这根管道也只能运送容量之内的。在这个自来水系统中有一个超级无敌牛逼的无限出水水库被称为源点和一个无限吃水的超级无敌牛逼小区被称为汇点。

这个自来水系统满足管道的中间不会有水的残留或者溢出，而且在流动的过程中并不会有新的水加入，并且水库与小区并不在一起。其中，容量指单位时间最多可以通过的水，流量表示单位时间实际流过的水，剩余容量表示容量减去流量也就是浪费的流量。