短时间内可能会不时更新这个系列,学了网络流的新东西或新题就扔在这吧,望周知。
最大流
性质:
设 \(f(u,v)\) 表示 \(u \rightarrow v\) 的流量, \(c(u,v)\) 表示 \(u \rightarrow v\) 的限制。
-
\(f(u,v) \le c(u,v)\) (显然)
-
\(f(u,v) = -f(v,u)\) 可以理解为 \(u\) 向 \(v\) 流 \(x\) 的流量,相当于 \(v\) 向 \(u\) 流 \(-x\) 的流量。
-
\(\sum_{u,v} f(u,v) = 0\)(希望读者自证)