更新日志

2024/12/31：开工。添加网络流概念以及EK算法

概念

官方定义

OI-wiki

网络

一种特殊有向图，有一个源点 \(s\) 与汇点 \(t\)。

图中每一条边都具有容量 \(c\)，也就是流经流量上限。不存在的边 \(c=0\)。

可以视作流水，从源点开始进水（无限或有限），通过一条条边流开，每条边的尺寸限定了流量。

流

一个整体，大概就是所有有流水的边。

割

两个点集合 \(S,T\)，满足 \(S\cup T=V\) 且 \(S\cap T=\varnothing\)，同时 \(s\in S,t\in T\)。

一个割的容量是 \(\sum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)\)。