526互联

浅谈网络流

发布时间 2023-12-29 21:25:30作者: FAKUMARER

浅谈网络流

最近网络流做了一堆，感觉有微弱的进步！

记录一些 好的套路，好的错误，以便以后再错

板子

根据地方法律法规，最大流 中 \(Dinic\) 以及 费用流 中 \(EK\) 不应当被卡，望周知

下面并没有出现 \(HLPP\) 的任何板子

因为这个东西 十分的难调 并 理论时间复杂度很对（一定不是指 上界极紧）

导致我根本不会写（根本原因）

最大流

多用各种 增广路算法，下面给出 两种常用算法实现

容易被卡，而且 绝绝绝大多数情况下 能被 \(Dinic\) 平替的 \(EK\) 就直接跳了

最大流增广路 大体思路 就是每次找一条 可行通路，增流到 被塞满了！

然后有一层的边 都被塞满了！

于是 进不去，怎么想也进不去吧！（指流量）

就结束了

最大流的正确性很显然 —— \(\textsf {Meatherm}\)


\(Dinic\)

namespace Dinic {
	const int MAXN = 100005;
	const long long INF  = 1e16;
	
	struct Node {
		int to, nxt;
		long long f;
	} E[MAXN << 1];
	
	int H[MAXN], tot = 1;
	
	inline void Add_Edge (const int u, const int v, const long long f) {
		E[++ tot] = {v, H[u], f}, H[u] = tot;
		E[++ tot] = {u, H[v], 0}, H[v] = tot;
	}
	
	int S, T;
	int Cur[MAXN], Dep[MAXN];
	
	inline bool BFS () {
		fill (Dep, Dep + MAXN, -1);
		queue <int> q;
		q.push (S), Dep[S] = 0, Cur[S] = H[S];
		int u, v, f;
		while (!q.empty ()) {
			u = q.front (), q.pop ();
			for (int i = H[u]; i; i = E[i].nxt) {
				v = E[i].to, f = E[i].f;
				if (Dep[v] == -1 && f) {
					Dep[v] = Dep[u] + 1, Cur[v] = H[v], q.push (v);
					if (v == T) return 1;
				}
			}
		}
		return 0;
	}
	
	inline long long DFS (const int x, const long long MAXF) {
		if (x == T || MAXF == 0) return MAXF;
		long long F = 0;
		for (int i = Cur[x]; i && F < MAXF; i = E[i].nxt) {
			Cur[x] = i;
			if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
				long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
				if (!TmpF) Dep[E[i].to] = -1;
				F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
			}
		}
		return F;
	}
	
	inline long long dinic () {
		long long F = 0;
		while (BFS ()) F += DFS (S, INF);
		return F;
	}
}

注意 当前弧优化 的实现！

考虑这个东西 我曾经写过 以下 3 * 3 种方式，感觉把 能错的都错了

在初始化上 

inline bool BFS () {
    fill (Dep, Dep + MAXN, -1);
    queue <int> q;
    q.push (S), Dep[S] = 0, Cur[S] = H[S]; // 开头特判源点
    int u, v, f;
    while (!q.empty ()) {
        u = q.front (), q.pop ();
        for (int i = H[u]; i; i = E[i].nxt) {
            v = E[i].to, f = E[i].f;
            if (Dep[v] == -1 && f) { // 每次初始化 边终点 (E[i].to)
                Dep[v] = Dep[u] + 1, Cur[v] = H[v], q.push (v);
                if (v == T) return 1;
            }
        }
    }
    return 0;
}

这个第一种写法是对的，考虑每个点 \(Dep\) 都将被更新到，后面 \(DFS\) 可以正常执行多路增广。

这个写法就是要注意 特判源点，但不需要额外辅助变量，时间也很对，十分规范！


inline bool BFS () {
    fill (Dep, Dep + MAXN, -1);
    for (int i = 1; i <= N; ++ i) Cur[i] = H[i];
    // or memcpy (Cur, H, sizeof H); 在开头统一初始化
    queue <int> q;
    q.push (S), Dep[S] = 0;
    int u, v, f;
    while (!q.empty ()) {
        u = q.front (), q.pop ();
        for (int i = H[u]; i; i = E[i].nxt) {
            v = E[i].to, f = E[i].f;
            if (Dep[v] == -1 && f) {
                Dep[v] = Dep[u] + 1, q.push (v);
                if (v == T) return 1;
            }
        }
    }
    return 0;
}

这个第二种写法也是对的，在 开头全部复制 这个一听就不可能有问题。

但是你要么需要把 \(N\) 写在函数前面（本人习惯板子单独放前面，所以 \(N\) 一般在后面）

要么 \(memset\) 一整个数组（当你数组大小和实际点数差异大时，会浪费很多时间）

总之不很完美


inline bool BFS () {
    fill (Dep, Dep + MAXN, -1);
    queue <int> q;
    q.push (S), Dep[S] = 0;
    int u, v, f;
    while (!q.empty ()) {
        u = q.front (), q.pop (), Cur[u] = H[u]; // 每次初始化 边起点
        for (int i = H[u]; i; i = E[i].nxt) {
            v = E[i].to, f = E[i].f;
            if (Dep[v] == -1 && f) {
                Dep[v] = Dep[u] + 1, q.push (v);
                if (v == T) return 1;
            }
        }
    }
    return 0;
}

这个第三种写法就很错了，而我甚至在 相当长一段时间 都是这么写的

（因为他确实比前面俩简单

仔细思考会发现，它只更新到 第一个能到达汇点的点，然后就 退出了！

于是 十分逆天，这玩意儿直接退化成了 \(EK\)（在 \(DFS\) 的时候每次只有 一路可用）


讲一个 题 外 话

在 费用流 的 \(SPFA\) 实现中，第三种写法并无问题

原因显然，\(SPFA\) 的实现中 并不允许到汇点就提前跳出


在使用上

也可以看这个

for (int i = Cur[x]; i && F < MAXF; i = E[i].nxt) {
	Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	// if (F >= MAXF) break;
}

这个第一种写法是对的，不取地址，手动记录

然后你 \(F < MAXF\) 的判断就可以放在循环里（虽然很容易忘）

相当的规范，我十分喜欢！


for (int &i = Cur[x]; i; i = E[i].nxt) {
	// Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	if (F >= MAXF) break;
}

这个第二种写法也是对的，可取地址，不用写 \(Cur[x] = i\) 这个东西

但是 \(F\) 和 \(MAXF\) 但判断要 在循环末尾写出来，不很美观


for (int &i = Cur[x]; i && F < MAXF; i = E[i].nxt) {
	// Cur[x] = i;
	if (Dep[E[i].to] == Dep[x] + 1 && E[i].f) {
		long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
		if (!TmpF) Dep[E[i].to] = -1;
			F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
	}
	// if (F >= MAXF) break;
}

这个第三种写法就很错了，感觉上就是把前两种结合起来吧？

但事实上这个十分的假，每次都会增广不完，效率低下

根据考证，问题还是出在 循环条件执行顺序 的理解上

考虑原来理解循环的顺序是 先执行判断，再执行赋值

但事实上，完整的 循环执行步骤 是这样的：


（第一次执行时）1.执行 for 的 第一语句
（第一次执行时）2.判断 for 的 第二语句
（后续循环）{
	1.循环第一行
	2.循环最后一行
	3.执行 for 的第三语句
	4.判断 for 的第二语句
}

比较神秘，带进去就可以很快判断出三种写法 对为什么对，错为什么错（


一些 容易忘 的地方

1.建边

  • 单向边反边 流量为 0，双向边反边 流量为 \(f\)
  •  \(tot\) 初始值为 1 ！！！！！
  • 开 边集数组 \(E\) 时，大概率 \(<< 1\) 是不够的
  • 注意 源汇 及 其它点 编号是否 大于 \(MAXN\)

2.BFS

  • 特判 源点当前弧，当前弧，当前弧！！！
  • \(q.pop () ~~ q.push(v)\) 一生之敌
  • 不要写成 \(SPFA\) 还加个 \(Vis\)，这显得很傻

3.DFS

  • 开局是 \(return ~ MAXF\) 不是 \(return ~ 0\) ！
  • 记得判断 \(F < MAXF\)
  • 记得最后 \(return ~ F\)

感觉上述问题每次总会 随机一个 出现，火大！

yny の 神 秘 优 化
namespace Dinic {
	struct Edge {
		int u, v;
		long long w;
		
		inline bool operator < (const Edge &a) const {
			return w > a.w;
		}
	};
	
	struct Node {
		int to, id;
		long long f;
	};
	
	vector <Edge> Tmp;
	vector <Node> E[MAXN];
	
	int Now[MAXN];
	
	inline void Add_Edge (const int u, const int v, const long long w) {
		Tmp.push_back ({u, v, w});
	}
	
	inline void add_edge (const int x) {
		E[Tmp[x].u].push_back ({Tmp[x].v, Now[Tmp[x].v] ++, Tmp[x].w});
		E[Tmp[x].v].push_back ({Tmp[x].u, Now[Tmp[x].u] ++, 0});
	}
	
	int Cur[MAXN], Dep[MAXN];
	int S, T;
	
	inline bool BFS () {
		memset (Cur, 0, sizeof Cur);
		memset (Dep, 0, sizeof Dep);
		queue <int> q; 
		q.push (S), Dep[S] = 1;
		int u;
		while (!q.empty ()) {
			u = q.front (), q.pop ();
			for (auto i : E[u]) 
				if (!Dep[i.to] && i.f) {
					Dep[i.to] = Dep[u] + 1, q.push (i.to);
					if (i.to == T) return 1;
				}
		}
		return 0;
	}
	
	inline long long DFS (const int x, const long long MAXF) {
		if (x == T || MAXF == 0) return MAXF;
		long long f = 0;
		for (int i = Cur[x]; i < (int) E[x].size () && f < MAXF; ++ i) {
			Cur[x] = i;
			if (Dep[E[x][i].to] == Dep[x] + 1 && E[x][i].f) {
				long long TmpF = DFS (E[x][i].to, min (MAXF - f, E[x][i].f));
				if (!TmpF) Dep[E[x][i].to] = 0;
				f += TmpF, E[x][i].f -= TmpF, E[E[x][i].to][E[x][i].id].f += TmpF;
			}
		}
		return f;
	}
	
	inline long long Solve () {
		long long f = 0;
		while (BFS ()) f += DFS (S, INF);
		return f;
	}
	
	inline long long dinic () {
		sort (Tmp.begin(), Tmp.end());
		long long Ans = 0;
		for (int i = 1e9, j = 0; j < (int) Tmp.size(); i /= 20) {
			while (Tmp[j].w >= i && j < (int) Tmp.size()) add_edge (j), ++ j;
			Ans += Solve ();
		}
		return Ans;
	}
}

本质上是 按值域分块加边，把 相近流量 的边 放在一起

块长 这个东西每次 \(\div 20\) 十分合适，也有 \(<< 4\) 之类的，动态调整就好

需要用 \(vector\) 来存边，初始加边只是存入，真正跑之前再 排序 并 加边

能轻松跑过 Luogu P4722 【模板】最大流 加强版 / 预流推进 什么实力不用多说

但是这个优化很玄学，就...（一直不知道在理论复杂度上真的有优化吗？

然后显然，这东西并不能在 动态加边 的过程中 保持良好的复杂度

因为本身就是 先把边集离线了 然后特定方式加边

有一定局限性，但还是很值得学

费用流 似乎也能应用 这个东西？没有仔细研究过 正确性 上的证明？

我实现过一份，但是板子题 \(60~pts ~~ TLE\) 了，有种卡死的感觉

其它点倒没有 \(WA\)

先鸽了，会的 \(DALAO\) 教教！！！

\(ISAP\)

注意，以下板子 有可能 是假的！

主要是因为按理说 这玩意儿 要比 上面那玩意儿 快一些

但我写 这篇随笔 之前专门去测了一下...（Luogu P3376 | P4722）

嘶，效果并不理想（至少在 板子题上）

namespace _ISAP {
	struct Edge {
		int to, nxt;
		long long f;
	} E[MAXN << 1];
	
	int H[MAXN], tot = 1, N; // FUCK
	
	inline void Add_Edge (const int u, const int v, const int f) {
		E[++ tot] = {v, H[u], f}, H[u] = tot;
		E[++ tot] = {u, H[v], 0}, H[v] = tot;
	}
	
	int Dep[MAXN], Gap[MAXN], Cur[MAXN];
	int S = 11451, T = 19198;
	
	inline void BFS () {
		memset (Dep, -1, sizeof Dep);
		memset (Gap, 0, sizeof Gap);
		queue <int> q;
		q.push (T), Gap[0] = 1, Dep[T] = 0;
		int u, v;
		while (!q.empty ()) {
			u = q.front (), q.pop ();
			for (int i = H[u]; i; i = E[i].nxt) {
				v = E[i].to;
				if (Dep[v] != -1) continue;
				q.push (v), Dep[v] = Dep[u] + 1, ++ Gap[Dep[v]];
			}
		}
		return;
	}
	
	inline long long DFS (const int x, const long long MAXF) {
		if (x == T) return MAXF;
		long long F = 0;
		for (int i = H[x]; i; i = E[i].nxt) {
			if (E[i].f && Dep[E[i].to] + 1 == Dep[x]) {
				long long TmpF = DFS (E[i].to, min (E[i].f, MAXF - F));
				if (TmpF) F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF;
				if (F == MAXF) return F;
			}
		}
		-- Gap[Dep[x]];
		if (Gap[Dep[x]] == 0) Dep[S] = N;
		Gap[++ Dep[x]] ++;
		return F;
	}
	
	inline long long ISAP () {
		long long F = 0;
		BFS ();
		while (Dep[S] < N) F += DFS (S, INF);
		return F;
	}
}

这个东西的优化 讲人话就是 省掉了多次 \(BFS\)

通过 \(Gap\) 数组记录每个 \(Dep\) 的点数，由于 \(BFS\) 是反向跑的

然后每次把当前点 增广完之后就更新当前点 \(Dep\)（当前点不可用了）

那么显然 如果源点 \(S\) 的 \(Dep\) 被推到 \(N\)，或者说出现了 断层（没法联通了）

那就完了！返回最大流就行

问题是这东西丑就丑在你需要 把 \(N\) 放在前面！！！

没有一点好！！！！！

但不然的话 第一个结束条件 就没法判，时间会很有问题

 其他的各种算法 还是 看板子题题解 来的好，我不了解的也就不写了

费用流

即 最小费用最大流，但是 板子可以用到各种地方

不排除 当你懒得改板子的时候 甚至可以拿来写 最大流

下面将给出一种 垃圾的增广路实现 并 使得它变强的办法

以及一种 本身就非常强的 单纯形实现

\(Dinic\)

实现

先讲实现，本质就是从 最大流 \(Dinic\) 扩展而来

把 \(BFS\) 部分改成 您喜欢的 最短路算法（\(SPFA, Dijkstra...\) 都行）

边权就是 边上费用，\(DFS\) 增流时 统计费用 即可

注意由于 反边大多情况下是带负权的，所以此处的 \(Dijkstra\) 实现参考 \(Johnson\) 全源最短路，需要先跑一遍 \(Bellman-Ford ~ / ~ SPFA\) 来 处理负边权问题（设计势能）。

考虑到上面的问题，显然 \(Dijkstra\) 实现 并不支持动态加边

（不然你加一次，跑一次 \(SPFA\) 处理，不如直接 \(SPFA\)）

并且 常数 和 堆的实现 有很大关系

（这导致在 \(C++\) 语言下是否打开 \(O2\) 对其影响是 致命的）

有一定局限性，就不写了（

\(SPFA + Dinic\) 实现

namespace MCMF {
	struct Node {
		int to, nxt;
		long long f, w;
	} E[MAXN << 1];
	
	int H[MAXN], tot = 1;
	
	inline void Add_Edge (const int u, const int v, const long long f, const long long w) {
		E[++ tot] = {v, H[u], f, + w}, H[u] = tot;
		E[++ tot] = {u, H[v], 0, - w}, H[v] = tot;
	}
	
	bool Vis[MAXN];
	int S, T;
	int Dis[MAXN], Cur[MAXN];
	
	inline bool SPFA () {
		memset (Dis, 63, sizeof Dis);
		deque <int> q;
		q.push_front (S), Dis[S] = 0;
		int u, v, w, f;
		while (!q.empty ()) {
			u = q.front (), q.pop_front (), Vis[u] = 0, Cur[u] = H[u];
			for (int i = H[u]; i; i = E[i].nxt) {
				v = E[i].to, w = E[i].w, f = E[i].f;
				if (Dis[v] > Dis[u] + w && f) {
					Dis[v] = Dis[u] + w;
					if (!Vis[v]) {
						if (q.empty () || Dis[v] > Dis[q.front ()]) q.push_back (v), Vis[v] = 1;
						else q.push_front (v), Vis[v] = 1;
					}
				}
			}
		}
		if (Dis[T] < 1e9) return 1;
		return 0;
	} 
	
	long long MinC = 0;
	
	inline long long DFS (const int x, const long long MAXF) {
		if (x == T || MAXF == 0) return MAXF;
		Vis[x] = 1;
		long long F = 0;
		for (int i = Cur[x]; i && F < MAXF; i = E[i].nxt) {
			Cur[x] = i;
			if (!Vis[E[i].to] && Dis[E[i].to] == Dis[x] + E[i].w && E[i].f) {
				long long TmpF = DFS (E[i].to, min (MAXF - F, E[i].f));
				if (!TmpF) Dis[E[i].to] = -1;
				F += TmpF, E[i].f -= TmpF, E[i ^ 1].f += TmpF, MinC += TmpF * E[i].w;
			}
		}
		Vis[x] = 0;
		return F;
	}
	
	inline long long Dinic () {
		long long F = 0;
		while (SPFA ()) F += DFS (S, INF);
		return F;
	}
}

一些优化点
  1. 如果 建双向边 那么一般 只需要改动 \(Add\_Edge\) 使反边 流量 / 费用 等于正边即可
  2. 万恶的 当前弧！
  3. \(SPFA\) 可以应用 双向队列优化！
  4. 注意到其实 最后 \(while\) 里的 \(DFS\) 不需要再套 \(while\)，不知道以前在写啥（最大流 一样）
  5. yny の 神秘优化？

正确性？

前日与 \(\textsf {Meatherm}\) 先生讨论了这个实现的 正确性问题，豁然开朗！

首先十分重要的一点，基础的增广路算法 不能处理任何时候的 负圈

\(\textsf {Meatherm}\) 先生 那天提出一种情况

如果我现有边 \(A, B\) 并 \(Cost = 2, Flow = 1\)

再加入边 \(C\) 有 \(Cost = 1, Flow = 1\) 再跑一次

最小费用是几喃？几费喃？三费！

然后可以尝试自己跑跑 平凡的增广路费用流 板子，\(MinCost = 4\) ！！！


S = 1, T = 3;
Add_Edge (1, 2, 1, 2);
Add_Edge (2, 3, 1, 2);
MCMF();
Add_Edge (1, 2, 1, 1); // Add_Edge (1, 2, 1, 3) is Right
MCMF();
cout << MINC << endl;
// 流程

（当然也很有可能直接 死循环）

怎么回事 呢？考虑第一次增广的时候，\(A, B\) 满流，于是反边有 \(1\) 的可用流量

加入 \(C\) 之后，显然 \(A\) 的反边和 \(C\) 形成了 负环！（隐藏负环 \(+1\)）寄！

（把 \(C\) 边权改成 \(> 2\) 就不会出事）

由此也启示出一个需要注意的点

基础的增广路算法 动态加边 的时候需注意 不能产生负环（不应出现 同流同起始边费用更小 之类的情况）

（但无需担心是否会在跑的时候产生 额外负环，考虑每次选的是 最短路，容易证明）

然后考虑为什么 最短增广路 就可以得到 最小费用最大流

我们似乎得出了一些 共同认同的 感性理解 以及 理性证明 如下

首先你的 最短路算法 显然是从 最大流 \(Dinic\) 的 \(BFS\) 扩展而来

保证有 可行流增广路 就 不会停止 的特性

那么在 这一部分

然后只需证明它能 取到最小费用 就行

感性理解 就是

我每次增广，走了 当前的最优解，留下了 给以后反悔用的边

每一次对 原图的影响 实质上相当于 选了一条边 并 反悔了一些边（就像 反悔贪心）

反边消除了 可能的后效性影响，于是直接做，就很对

理性一点的话

考虑我们 增流的过程，每次找 最短路 增流

设 \(F_i\) 在这个图上表示 流量为 \(i\) 时的最小费用

然后假使你 当前要增加 \(1\) 的流量，并且 无后效性

显然直接 贪心在最短路上增流 就行，于是一定有 \(F_{i + 1} = F_i + Dis_{S-T} * MinFlow\)

（\(MinFlow\) 是 最短路上的可行流量最小值）

到这里，正确性的问题差不多解决了（可能写的不是很清楚？）

\(Simplex\)

即 网络单纯形 法，由 线性规划问题 的 单纯形算法 变形而来

（循环流 可以规约成 线性规划问题的标准型，而 有源汇费用流 加边 就能变成循环流）

关于 线性规划 与 网络流 基本原理这一部分可以看 这个（感觉挺能懂的一个 课件）

这里只讲 算法步骤，实现细节 之类的

算法步骤
  1. 为了满足 线性规划标准形，我们先把图转成 循环流，也就是 \(T\) 向 \(S\) 连容量 \(INF\)，费用 \(-INF\) 边

这个也可以理解成为 找负环增流 做准备，因为多数情况下 建出的图没有负环，而加边后就构造出一个

  1. 之后我们找到一个 可行支撑树，也就是 单纯形算法中的 基

这里 可行支撑树 就是一棵树上都是 未满流边 的 生成树，也即 在支撑树上存在可行流

  1. 之后就开始 判负环，具体就是 枚举边，判断在 支撑树 上 加入该边后是否形成 负环

显然加入一边会形成一个 基环树，然后有一个 均摊十分快 的方法来判断 是否为负环，后面会讲

  1. 加入 这条边（入基边），然后 找到负环上剩余流量最小边，并在这个过程中 存下这个负环

注意还需存储 最小边的绝对位置 和 相对位置（在 入基边 左还是右）

  1. 然后 推流，给这个环上所有边都加上 最小剩余流量，同时 更新费用（流量 * 途径边费用）

推完流之后就会 把一条边塞满，对应 单纯形算法 中的 转轴变换（的前半部分）

即把 入基变量与离基变量 在单纯形表中交点格 变换成 \(0\)

  1. 推流 之后 重构可行支撑树，可以发现就是 反转入基边到删除边之间的链

这里 反转的具体起止点 需要根据相对位置 简单分讨，依旧 后面随代码讲

这一步就对应 转轴变换 的后一部分，入基变量入基，离基变量离基，重构单纯形表

  1. 返回这一次的 费用，累加到 \(MinCost\)，回到 \(Step~3\) 直到 图中没有负环

使得 没有更优的可能，对应使 所有非基本变量系数非负

  1. 现在 最大流 就是 \(Step ~ 1\) 中加上的 \(INF\) 边的流量，\(MinCost\) 要补上这个 最大流 * \(INF\)

考虑 循环流 保证流量平衡，故 \(S_{out} = S_{in}, T_{out} = T_{in}\)

那么显然，\(S_{out} -> T_{in}\) 就是理解的通常 最大流（在 不可增流时 从 \(S\) 流到 \(T\) 的流量）

然后 \(T_{out} -> S_{in}\) 就是初始加入的 \(INF\) 边，显然与 最大流 相等

补费用 这个操作十分容易理解，因为你 \(INF\) 边的有 额外的费用 \(-INF\)，不应计入答案

到此结束，可能看上去 有些抽象，下面举一个 特例 帮助理解

真的是特例，只是用于帮助理解的，不应在这里纠结 是否能推广的问题

假设原图是 一条链，链上每条边费用容量不等（容量均为 正值）

于是先 执行 \(Step~1\)，从 \(T\) 向 \(S\) 连了一条 \(INF\) 边，随后 构建支撑树（链的话好像...

显然这里 整个新图构成了一个负环，于是找到 环上流量最小的一条边

由于 \(T -> S\) 的边容量为 \(INF\)，显然剩余容量最小边在 原图上

然后 推流，也就是 给整个环加上等于最小边容量的流量，更新费用，重构支撑树

这里的 支撑树 就是 原图 - 容量最小边 + \(INF\) 边

回到 \(Step ~ 3\) 试图找负环，由于 唯一不在支撑树上的边（刚的容量最小边）满流了

找不到负环了，结束！费用加上 \(INF\) * 容量最小边容量

这时候检查我们得到的答案，最大流 就是 链上容量最小边容量

最小费用 是 最大流量 * 链上边费用和（刚刚 整个链都在负环 中，都被统计了）

很对吧，那么

你已经学会一条链的情况了，快推广到任意图吧！