首页 > 其他分享 >浅谈网络流

浅谈网络流

时间：2023-12-29 21:35:17浏览次数：27  
标签：return 浅谈 Dep TmpF 网络 long int MAXF

浅谈网络流

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

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

板子

根据地方法律法规，最大流 中 \(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\) * 容量最小边容量

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

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

很对吧，那么

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

标签：return,浅谈,Dep,TmpF,网络,long,int,MAXF
From： https://www.cnblogs.com/FAKUMARER/p/17934590.html

相关文章

  • 智安网络|2024年元旦假期值班安排
    ......
  • 开放网络+私有云=？星融元的私有云承载网络解决方案实例
    在全世界范围内的云服务市场上，开放网络一直是一个备受关注的话题。相比于传统供应商的网络设备，开放网络具备软硬件解耦、云原生、可选组件丰富等优势，对云服务商和超大型企业有足够的吸引力。SONiC作为开源的网络操作系统，使得新一代网络中的高级可编程性成为现实。在Gartner2023年......
  • 网络安全——SpringBoot配置文件明文加密
    信铁寒胜：这边文章真的说得挺好的。XTHS：第一步、XTHS：第二步、XTHS：第三步、XTHS：第四步！就可以实现了。（但是前提，你要先对你的文本进行加密，然后按照ENC(加密文本)，放到配置文件中） 一、前言在日常开发中，项目中会有很多配置文件。比如SpringBoot项目核心的数据库配置、Redis账号密码......
  • 6 浅谈XILINX FIFO的基本使用
    软件版本：VIVADO2021.1操作系统：WIN1064bit硬件平台：适用XILINXA7/K7/Z7/ZU/KU系列FPGA登录米联客(MiLianKe)FPGA社区-www.uisrc.com观看免费视频课程、在线答疑解惑！1概述首先来大概了解下什么是FIFO,FIFO(FirstInputFirstOutput)简单说就是指先进先出。FIFO也是缓存机......
  • 27 浅谈XILINX BRAM的基本使用
    软件版本：VIVADO2021.1操作系统：WIN1064bit硬件平台：适用XILINXA7/K7/Z7/ZU/KU系列FPGA登录米联客(MiLianKe)FPGA社区-www.uisrc.com观看免费视频课程、在线答疑解惑！1概述对于BRAM详细的说明在XILINX官方文档，pg058中有说明，我们这里仅对课程涉及的内容讲解。Xlinx系列FPGA......
  • 浅谈10kV站所柜内运行状态及环境指标监测管理平台分析
    安科瑞张田田摘要：在整个电能管理系统中，配电室综合监控占据着重要的位置。现阶段，配电室通常均运用无人值守、定时巡查制度，此方式不仅需要投入诸多的物力与人力，同时也不能实时监控配电室的安全与环境。而配电室环境的可靠性与稳定性直接影响着变压器等设备的正常运行。对此，主要对10kV......
  • EventLog Analyzer：优化企业网络安全的不可或缺之选
    随着企业信息技术的不断发展，网络安全问题也变得日益严峻。在这个数字化时代，企业网络日志收集变得尤为重要，以便及时发现和应对潜在的威胁。在众多网络日志管理工具中，EventLogAnalyzer凭借其卓越的功能和易用性成为企业网络安全的不可或缺之选。EventLogAnalyzer1.强大的日志收集......
  • 浅谈居民小区配电房动力环境监控系统研究与应用
    安科瑞张田田摘要：智配电站动力环境监控系统通过构建三级监控网络，基于TCP/IP网络协议作为通讯构架，组建IP网络与监控中心进行传输。实现对配电站房的远程监控管理。同时采用了集中式管理模式，快速实现区域内配电站房的有效覆盖，为用户提供配电站所的配变电压、电流、有功功率、无功......
  • 网络安全漏洞的种类分为哪些?
    漏洞，是指在硬件、软件、协议的具体实现或系统安全策略上存在的缺陷，从而可以使攻击者能够在未授权的情况下访问或破坏系统。漏洞的出现，不仅会造成个人隐私信息泄露，还涉及到我们的财产安全，那么网络安全漏洞的种类分为哪些?接下来小编就带大家认识一下吧。第一：软件漏洞任......
  • 权威认证｜智安云平台荣获公安部首批网络安全产品认证
    近日，智安网络云综合防御平台V3.0通过公安部复杂专业的安全测试，荣获了网络安全产品认证证书，据悉，这是公安部颁发的首批证书。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99