网络单纯形算法是一种神奇的算法。它可以求解带负圈的费用流，可以过 HLPP 板子，但它的（最坏）复杂度好像是指数级，尽管我并不会证
感性理解：它和线规算法 simplex 有许多相似之处，而 simplex （最坏）是指数级的.
虽然但是，据 CF[1] 上所讲，它的平均时间复杂度是 \(O(VE)\)，且常数较小（无 LCT 情况下）.
网络单纯形算法用来求解无源汇最小费用可行流。将有源汇最小费用最大流转换为无源汇最小费用可行流的方法：从汇向源连一条费用为 \(-\infty\)，流量为 \(+\infty\) 的边。
大致思路：给定图 \(G=(V,E)\)，在算法过程中，我们维护它的生成森林边集 \(T\)，每次找一条不在 \(T\) 内的边 \(t \in E \setminus T\)，若 \(T \cup \{t\}\) 包含负环，则在 \(T\) 中沿此负环推流，选出一条满流的边删去，将 \(t\) 加入 \(T\). 重复此过程直到 \(T\) 中不含负环，此时我们就得到了 \(G\) 的最小费用可行流。
线规的解释：生成树相当于初始可行解，向负环推流相当于转动变量。
判断一条边加入生成树后是否有负环
考虑一个权重函数 \(h(a),a \in V\)，满足对 \(\forall e \in T, h(e.\text{to}) - h(e.\text{from}) = e.\text{cost}\)，那么对于两个点 \(a,b\)，\(h(a)-h(b)\) 就是 \(T\) 上 \(a\) 到 \(b\) 一条路的权值之和。对边 \(e \in E\)，若 \(h(e.\text{to}) - h(e.\text{from}) + e.\text{cost} < 0\)，则它所在的环路（沿着它的方向）为负环。
找到负环后推流
先从 \(e.\text{from}\) 和 \(e.\text{to}\) 向上跳到 LCA，再从两边分别找能推的最小流值，最后推流。
这里如果用 LCT 维护，则可从 \(O(n)\) 优化到 \(O(\log n)\)，但常数大。
推流后，别忘了删边并反转被删的链的父子关系，保证生成树还是树。