网络流

不说废话。

概念

网络，对于一张有向连通图 \(G=(V,E)\)，其中分别有且仅有一个 \(s \in V,t \in V\)，且 \(s\) 无入度，\(t\) 无出度，则我们称 \(G\) 是一个网络。其中我们称 \(s\) 为源点，\(t\) 为汇点。

对于一个网络，其需要满足一下性质：

对于一条边 \((u,v) \in E\)，定义 \(f(u,v)\) 为其流量，\(c(u,v)\) 为其容量，且要求 \(f(u,v) \le c(u,v)\)。
对于一个点 \(u \in V\)，称其净流量为其总流入减总流出，且除了 \(s\) 和 \(t\) 外，要求其流入等于其流出，即对于任意 \(u \ne {s,t}\)，\(u\) 的净流量为 \(0\)。

定义一个边 \((u,v)\) 的剩余容量为其 \(f(u,v)-c(u,v)\) 即容量减流量，记作 \(c_f(u,v)\)。定义剩余流量不为 \(0\) 的边和节点构成的子图为残量网络。记作 \(G_f\)。

不难发现，\(s\) 的流出等于 \(t\) 的流入。我们称整个网络的流为 \(s\) 的流出即 \(t\) 的流入。

我们把 \(G_f\) 中一条 \(u\) 到 \(v\) 的路径称作增广路。

我们对于一条增广路，给每一条边都加上一个相等的流量，我们称这个过程为增广。

另外，反向边为一条 \(G\) 中一条边的反向边即 \((v,u)\)，且 \(f(v,u) = -f(u,v)\)。

最大流

对于一个网络，找到一个流，使得流的流量最大。

板子题：

P3376 【模板】网络最大流

给定一个网络以及其源点、汇点，求其网络最大流。

\(1 \le n \le 200\), \(1 \le m \le 5000\)，\(0 \le w \le 2^{31}\)。

FF 算法

FF 算法即 Ford-Fulkerson 算法。

首先考虑最暴力的策略。每次只要找到一条增广路，便对他进行增广。重复此流程，直到网络中不存在增广路。

显然，这个是假的贪心。随意找一个例子就可以卡掉。

我们拿下面的这幅图举例子（如图 1，图中边权标注的是剩余容量）。首先我们找到一条增广路 \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) 并且对他进行增广，这些边剩余容量变为 \(0\)。然后图中不存在其余增广路（如图 2），最终求得此网络的流为 \(1\)。

o_260111075927_dfkajijhah.png (962×473) (cnblogs.com)

然而，不难发现，如果我们对于 \(1 \rightarrow 3 \rightarrow 4\) 和 \(1 \rightarrow 2 \rightarrow 4\) 分别进行增广，得到的流量为 \(2\)。

为了解决这样的问题，我们引入反向边，反向边为一条 \(G\) 中一条边的反向边即 \((v,u)\)，且我们约定 \(f(v,u) = -f(u,v)\)。为了满足这样的性质，在对 \((u,v)\) 的流量加 \(val\) 时，需要给其反向边的流量减 \(val\)。

以此，我们可以借助反向边解决问题。（如图 3）

我们不妨将反向边当作正常的边进行处理。

o_260111081300_faudsiafu.png (1064×380) (cnblogs.com)

我们还是正常找一条增广路进行增广，然后这条增广路上的边的流量增加，同时其反向边的流量相应的减少，其剩余流量自然跟随变化（如图 4）。但是此时，我们在进行以此增广之后，你就发现你还可以找到一条增广路 \(1 \rightarrow 3 \rightarrow 2 \rightarrow 4\)，对他进行增广。进行完这些操作后，得到最大流量 \(2\)（如图 5）。

仔细观察不难发现，第二次增广时，当 \((2,3)\) 的反向边被增广后，\((2,3)\) 相当于没有被增广过。所以，反向边相当于一个“撤销”操作。

这就是 FF 算法的核心思想。可以使用 DFS 实现。但是时间复杂度过高。下面考虑优化。

EK 算法

EK 算法即 Edmonds-Karp 算法。核心思想在于利用 bfs 进行 FF 增广。

大致流程如下：

在 \(G_f\) 上找一条增广路。
在增广路上求出剩余容量的最小值，然后给增广路上边的流量加上他，给对应的反向边的容量减去他。
重复 1、2，直到没有增广路。

依此，便可以求出该网络的最大流量。单轮增广的时间复杂度为 \(O(E)\)，增广轮数理论上界为 \(O(VE)\)，那么 EK 算法总的时间复杂度为 \(O(VE^2)\)。

Dinic 算法

Dinic 算法是求解最大流问题的主流算法。是对于 FF/EK 的优化。

对于每一次增广，首先 bfs 对图按照 \(dis(s,u)\) 进行分层。我们让每个点 \(u\) 只能向自己的下一层的点 \(v\) 进行增广。这样每次增广的都是原图中边数最少的路径，且可以保证不会因为反向边的缘故让接下来的 dfs 陷入死循环。

分层之后，从 \(s\) 开始 dfs。区别于 EK，我们对于一个点 \(u\)，如果他从他的一个儿子找到了增广路，不必回到 \(s\) 进行再次处理，可以直接继续从 \(u\) 进行增广。

然后我们就可以写出复杂度较为正确的求最大流代码。

点击查看代码

#include <bits/stdc++.h>
#define il inline
#define int long long

using namespace std;

bool Beg;
namespace Zctf1088 {
namespace IO {
	const int bufsz = 1 << 20;
	char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
	#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
	il int read() {
		int x = 0; char ch = getchar(); bool t = 0;
		while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}
		while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
		return t ? -x : x;
	}
	char obuf[bufsz], *p3 = obuf, stk[50];
	#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
	#define putchar(ch) (p3 == obuf + bufsz && flush(), *p3++ = (ch))
	il void write(int x, bool t = 0) {
		int top = 0;
		x < 0 ? putchar('-'), x = -x : 0;
		do {stk[++top] = x % 10 | 48; x /= 10;} while(x);
		while (top) putchar(stk[top--]);
		t ? putchar(' ') : putchar('\n');
	}
	struct FL {
		~FL() {flush();}
	} fl;
}
using IO::read; using IO::write;
const int N = 205, M = 1e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, S, T;
struct Edge {
	int nxt, to, w;
} edge[M];
int head[M], tot = 1;
il void addEdge(int x, int y, int w) {
	edge[++tot] = {head[x], y, w};
	head[x] = tot;
}
int dis[N];
queue<int> q;
il bool bfs() {
	for (int i = 1; i <= n; i++) dis[i] = 0;
	while (!q.empty()) q.pop();
	q.push(S);
	dis[S] = 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = edge[i].nxt) {
			int y = edge[i].to, w = edge[i].w;
			if (w > 0 && dis[y] == 0) {
				dis[y] = dis[x] + 1;
				if (y == T) return true;
				q.push(y);
			}
		}
	}
	return false;
}
il int dfs(int x, int flow) {
	if (x == T) return flow;
	int rest = flow;
	for (int i = head[x]; i; i = edge[i].nxt) {
		int y = edge[i].to, w = edge[i].w;
		if (w > 0 && dis[y] == dis[x] + 1) {
			int k = dfs(y, min(rest, w));
			rest -= k;
			edge[i].w -= k;
			edge[i ^ 1].w += k;
		}
	}
	return flow - rest;
}
il int dinic() {
	int res = 0;
	while (bfs()) res += dfs(S, INF);
	return res;
}
signed main() {
	n = read(), m = read(), S = read(), T = read();
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read(), w = read();
		addEdge(x, y, w);
		addEdge(y, x, 0);
	}
	write(dinic());
    
	return 0;
}}
bool End;
il void Usd() {cerr << "\nUse: " << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {
	Zctf1088::main();
	Usd();
	return 0;
}

但是这篇代码依然无法通过最大流板子题。

我们需要一个优化：当前弧优化。

考虑对于一个节点，从他的一个儿子走下去找到了增广路回来后，一定是一下两种情况之一：

当前节点的流入还有剩余，说明从这个儿子走下去已经没有剩余容量了，从这个儿子走下去已经被填满了。那么以后就没有必要再走这个节点了。
当前节点的流入没有剩余，说明从这个儿子走下去可能还有剩余，但是后面的儿子给到的流出一定是 \(0\)，因为当前节点已经没有剩余的流了。直接 break 掉即可。

无论是以上两种情况，我们都会发现，我们再次到这个节点时，肯定就不需要再走这个儿子之前的儿子了，因为他们肯定已经被处理完了。那么我们每次走到 \(u\) 的一个儿子 \(v\)，就令 \(cur_u=v\)，下一次就不从 \(head_u\) 开始遍历，而是 \(cur_u\)。

那么就考虑在实现 dinic 时加上面三条优化。

于是我们 dinic 的复杂度就可以得到保证。时间复杂度为 \(O(V^2E)\)。

点击查看代码

#include <bits/stdc++.h>
#define il inline
#define int long long

using namespace std;

bool Beg;
namespace Zctf1088 {
namespace IO {
	const int bufsz = 1 << 20;
	char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
	#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
	il int read() {
		int x = 0; char ch = getchar(); bool t = 0;
		while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}
		while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
		return t ? -x : x;
	}
	char obuf[bufsz], *p3 = obuf, stk[50];
	#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
	#define putchar(ch) (p3 == obuf + bufsz && flush(), *p3++ = (ch))
	il void write(int x, bool t = 0) {
		int top = 0;
		x < 0 ? putchar('-'), x = -x : 0;
		do {stk[++top] = x % 10 | 48; x /= 10;} while(x);
		while (top) putchar(stk[top--]);
		t ? putchar(' ') : putchar('\n');
	}
	struct FL {
		~FL() {flush();}
	} fl;
}
using IO::read; using IO::write;
const int N = 205, M = 1e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, S, T;
struct Edge {
	int nxt, to, w;
} edge[M];
int head[M], tot = 1, cur[M];
il void addEdge(int x, int y, int w) {
	edge[++tot] = {head[x], y, w};
	head[x] = tot;
}
int dis[N];
queue<int> q;
il bool bfs() {	// 判断有无增广路并对图进行分层
	for (int i = 1; i <= n; i++) dis[i] = 0, cur[i] = head[i];
	while (!q.empty()) q.pop();
	q.push(S);
	dis[S] = 1;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = edge[i].nxt) {
			int y = edge[i].to, w = edge[i].w;
			if (w > 0 && dis[y] == 0) {
				dis[y] = dis[x] + 1;
				if (y == T) return true;
				q.push(y);
			}
		}
	}
	return false;
}
il int dfs(int x, int flow) {	// 上一层传入的流量
	if (x == T) return flow;	// 找到汇点返回
	int rest = flow;	// 当前节点剩余的可分配流量
	for (int i = cur[x]; i && rest; i = edge[i].nxt) {
		cur[x] = i;	// 当前弧优化
		int y = edge[i].to, w = edge[i].w;
		if (w > 0 && dis[y] == dis[x] + 1) {// 还有剩余流量在下一层
			int k = dfs(y, min(rest, w));	// 计算下面层能经过的流量
			if (k == 0) dis[y] = 0;
			rest -= k;
			edge[i].w -= k;		// 剩余流量减少
			edge[i ^ 1].w += k;	// 反向边剩余流量增加
		}
	}
	return flow - rest;
}
il int dinic() {
	int res = 0;
	while (bfs()) res += dfs(S, INF);	// 重复找增广路并 dfs 的过程直到没有增广路
	return res;
}
signed main() {
	n = read(), m = read(), S = read(), T = read();
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read(), w = read();
		addEdge(x, y, w);
		addEdge(y, x, 0);	// 加反向边
	}
	write(dinic());
	
	return 0;
}}
bool End;
il void Usd() {cerr << "\nUse: " << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {
	Zctf1088::main();
	Usd();
	return 0;
}

经过后期写题的调整，有一个比较实用的版本：

点击查看代码

struct Edge {
	int nxt, to, w;
} edge[M];
int head[N], cur[N], etot = 1;
il void addEdge(int x, int y, int w) {
	edge[++etot] = {head[x], y, w};
	head[x] = etot;
}
il void addEdge1(int x, int y, int w) {
	addEdge(x, y, w);
	addEdge(y, x, 0);
}
int dis[N], S, T;
queue<int> q;
il bool bfs(int n) {
	for (int i = 1; i <= n; i++) cur[i] = head[i], dis[i] = 0;
	while (!q.empty()) q.pop();
	dis[S] = 1; q.push(S);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = edge[i].nxt) {
			int y = edge[i].to, w = edge[i].w;
			if (w > 0 && !dis[y]) {
				dis[y] = dis[x] + 1;
				if (y == T) return true;
				q.push(y);
			}
		}
	}
	return false;
}
il int dfs(int x, int flow) {
	if (x == T) return flow;
	int rest = flow;
	for (int i = cur[x]; i && rest; i = edge[i].nxt) {
		cur[x] = i;
		int y = edge[i].to, w = edge[i].w;
		if (w > 0 && dis[y] == dis[x] + 1) {
			int k = dfs(y, min(rest, w));
			if (k == 0) dis[y] = 0;
			rest -= k;
			edge[i].w -= k;
			edge[i ^ 1].w += k;
		}
	}
	return flow - rest;
}
il int dinic(int n, int s, int t) {
	S = s, T = t;
	int res = 0;
	while (bfs(n)) res += dfs(S, INF);
	return res;
}

最小割

定义

对于一个网络 \(G\)，将其划分为两个点集 \(S,T\)，且 \(s \in S,t \in T\)，则称 \(\{S,T\}\) 是 \(G\) 的一个割。

定义割 \(\{S,T\}\) 的容量为 \(\sum_{u \in S} \sum_{v \in T} c(u,v)\)。最小割即求这个容量的最小值。

最大流最小割定理

内容

对于一个网络，其最大流 \(f\)，和其最小割 \(\{S,T\}\)，有 \(|f|=||\{S,T\}||\)。

其中，\(|f|\) 为流 \(f\) 的流量，\(||\{S,T\}||\) 为割 \(\{S,T\}\) 的容量即 \(\sum_{u \in S} \sum_{v \in T} c(u,v)\)。

证明

证明两个引理。

引理 1

对于任意流 \(f\) 与割 \(\{S,T\}\)，有 \(|f| \le ||S,T||\)。

其中取等的情况当且仅当 \(\{(u,v),u\in S,v\in T\}\) 都是满流，且 \(\{(u,v),u\in T,v\in S\}\) 都是空流，即从 \(S\) 到 \(T\) 的边都是满流，从 \(T\) 到 \(S\) 的边都是空流。

下面的 \(f(x)\) 为 \(x\) 的净流量，\(f(x,y)\) 为边 \((x,y)\) 为的流量。

证明：

\[\begin{aligned} |f| & =f(s) \\ & =\sum_{u \in S} f(u) \\ & =\sum_{u \in S}\left(\sum f(u, v)-\sum f(v, u)\right) \\ & =\sum_{u \in S}\left(\sum_{v \in S} f(u, v)+\sum_{v \in T} f(u, v)-\sum_{v \in S} f(v, u)-\sum_{v \in T} f(v, u)\right) \\ & =\sum_{u \in S}\left(\sum_{v \in T} f(u, v)-\sum_{v \in T} f(v, u)\right)+\sum_{u \in S} \sum_{v \in S} f(u, v)-\sum_{u \in S} \sum_{v \in S} f(v, u) \\ & =\sum_{u \in S}\left(\sum_{v \in T} f(u, v)-\sum_{v \in T} f(v, u)\right) \\ & \leq \sum_{u \in S} \sum_{v \in T} f(u, v) \quad(\text {此时如果要取等就要让 }\{(u, v), u \in T, v \in S\} \text { 都是空流}) \\ & \leq \sum_{u \in S} \sum_{v \in T} c(u, v) \quad(\text {此时如果要取等就要让 }\{(u, v), u \in S, v \in T\} \text { 都是满流}) \\ & =\|S, T\| \end{aligned} \]

引理 1 证毕。

引理 2

对于任意一个网络，总会存在流 \(f\) 和割 \(\{S,T\}\) 使得 \(|f|=||S,T||\)。

证明：

考虑给出构造：考虑在一增广得到一个流 \(f\) 后，网络上不存在 \(s \leadsto t\)，这时 \(s\) 所在的联通块为 \(S\)，\(t\) 所在的联通块为 \(T\)，此时正边都被增广完了，反边容量都为 \(0\)，则有：\(\{(u,v),u\in S,v\in T\}\) 都是满流，且 \(\{(u,v),u\in T,v\in S\}\) 都是空流。

引理 2 证毕。

那么，对于最大流 \(f'\) 和最小割 \(\{S',T'\}\)，有：

由引理 1 得，\(|f'| \le ||S',T'||\)。
由引理 2 得，由于 \(|f'| \geq |f|,||S,T|| \geq ||S',T'||\)，而又必然存在 \(|f|=||S,T||\)，则可得 \(|f'| \geq ||S',T'||\)。

于是 \(|f'|=||S',T'||\)，最大流最小割定理得证。

最小割树

模板题：

P4897 【模板】最小割树（Gomory-Hu Tree）

给定一张 \(n+1\)（编号 \(0\) 到 \(n\)）个点 \(m\) 条边得无向连通图，多次询问两点之间的最小割。

\(1 \le n \le 500\)，\(0 \le m \le 500\)，\(0 \le Q \le 10^5\)。

我们定义两点之间的最小割：原图的每条边有一个割断它的代价，即为使得这两个点不连通的最小代价。

考虑建树。

首先，我们在当前的这张图中，任取两点 \(u,v\)，然后跑出他们之间的最小割 \(cut(u,v)\)。我们在新图（即建出来的最小割树）上连接 \(u,v\)，边权为 \(cut(u,v)\)。

不难发现，图中满流的边就是 \(u,v\) 的割。沿任意一个合法的割将原图分成两部分 \(U,V\)，然后分治求解。重复此流程，即可建出最小割树。

最小割树的性质在于：最小割树上的任意两点 \(u,v\)，他们在树上简单路径边权的最小值，即为他们在原图上的最小割。

点击查看代码

#include <bits/stdc++.h>
#define il inline
#define int long long

using namespace std;

bool Beg;
namespace Zctf1088 {
namespace IO {
	const int bufsz = 1 << 20;
	char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
	#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
	il int read() {
		int x = 0; char ch = getchar(); bool t = 0;
		while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}
		while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
		return t ? -x : x;
	}
	char obuf[bufsz], *p3 = obuf, stk[50];
	#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
	#define putchar(ch) (p3 == obuf + bufsz && flush(), *p3++ = (ch))
	il void write(int x, bool t = 0) {
		int top = 0;
		x < 0 ? putchar('-'), x = -x : 0;
		do {stk[++top] = x % 10 | 48; x /= 10;} while(x);
		while (top) putchar(stk[top--]);
		t ? putchar(' ') : putchar('\n');
	}
	struct FL {
		~FL() {flush();}
	} fl;
}
using IO::read; using IO::write;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5, M = 1e6;
int n, m;
struct node {
	int x, y, w;
} e[M];
struct Edge {
	int nxt, to, w;
} edge[M];
int head[N], cur[N], etot = 1;
il void addEdge(int x, int y, int w) {
	edge[++etot] = {head[x], y, w};
	head[x] = etot;
}
il void addEdge1(int x, int y, int w) {
	addEdge(x, y, w);
	addEdge(y, x, 0);
}
int dis[N], S, T;
queue<int> q;
il bool bfs(int n) {
	for (int i = 1; i <= n; i++) cur[i] = head[i], dis[i] = 0;
	while (!q.empty()) q.pop();
	dis[S] = 1; q.push(S);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = edge[i].nxt) {
			int y = edge[i].to, w = edge[i].w;
			if (w > 0 && !dis[y]) {
				dis[y] = dis[x] + 1;
				if (y == T) return true;
				q.push(y);
			}
		}
	}
	return false;
}
il int dfs(int x, int flow) {
	if (x == T) return flow;
	int rest = flow;
	for (int i = cur[x]; i && rest; i = edge[i].nxt) {
		cur[x] = i;
		int y = edge[i].to, w = edge[i].w;
		if (w > 0 && dis[y] == dis[x] + 1) {
			int k = dfs(y, min(rest, w));
			if (k == 0) dis[y] = 0;
			rest -= k;
			edge[i].w -= k;
			edge[i ^ 1].w += k;
		}
	}
	return flow - rest;
}
int vis[N];
il void solve(int x) {	// 将图割为两个部分
	vis[x] = 1;
	for (int i = head[x]; i; i = edge[i].nxt) {
		int y = edge[i].to, w = edge[i].w;
		if (w > 0 && !vis[y]) solve(y);
	}
}
il void init() {
	for (int i = 1; i <= etot; i++) edge[i] = {0, 0, 0};
	for (int i = 1; i <= n; i++) head[i] = vis[i] = 0;
	etot = 1;
	for (int i = 1; i <= m; i++) {
		addEdge1(e[i].x, e[i].y, e[i].w);
		addEdge1(e[i].y, e[i].x, e[i].w);
	}
}
il int dinic(int n, int s, int t) {	// 正常跑最小割（最大流）
	init();
	S = s, T = t;
	int res = 0;
	while (bfs(n)) res += dfs(S, INF);
	solve(S);
	return res;
}
struct edge1 {
	int y, w;
};
vector<edge1> G[N];
int p[N], p1[N], p2[N];
il void build(int l, int r) {	// 建树
	if (l >= r) return;
	int s = p[l], t = p[l + 1];	// 随便挑两个点
	int res = dinic(n, s, t);
	G[s].push_back({t, res});
	G[t].push_back({s, res});
	int tot1 = 0, tot2 = 0;		// 以下部分为分治求解
	for (int i = l; i <= r; i++) {
		if (vis[p[i]]) p1[++tot1] = p[i];
		else p2[++tot2] = p[i];
	}
	for (int i = 1; i <= tot1; i++) p[l + i - 1] = p1[i];
	for (int i = 1; i <= tot2; i++) p[l + tot1 + i - 1] = p2[i];
	build(l, l + tot1 - 1);
	build(l + tot1, r);
}
int dep[N], fa[N][22], mn[N][22];
il void dfs1(int x, int fath) {
	dep[x] = dep[fath] + 1;
	fa[x][0] = fath;
	for (int i = 1; i <= 20; i++) {
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
		mn[x][i] = min(mn[x][i - 1], mn[fa[x][i - 1]][i - 1]);
	}
	for (edge1 i : G[x]) {
		if (i.y == fath) continue;
		mn[i.y][0] = i.w;
		dfs1(i.y, x);
	}
}
il int getlca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 20; i >= 0; i--) 
		if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
	if (x == y) return x;
	for (int i = 20; i >= 0; i--) 
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
il int getkmn(int x, int k) {	// 倍增求解路径最小值
	int res = INF;
	for (int i = 0; i <= 20; i++) {
		if ((k >> i) & 1) {
			res = min(res, mn[x][i]);
			x = fa[x][i];
		}
	}
	return res;
}
il int getmn(int x, int y) {
	int lca = getlca(x, y);
	return min(getkmn(x, dep[x] - dep[lca]), getkmn(y, dep[y] - dep[lca]));
}
signed main() {
	n = read() + 1, m = read();
	for (int i = 1; i <= m; i++) {
		int x = read() + 1, y = read() + 1, w = read();
		e[i] = {x, y, w};
	}
	for (int i = 1; i <= n; i++) p[i] = i;
	build(1, n);
	dfs1(1, 0);
	int qq = read();
	while (qq--) {
		int x = read() + 1, y = read() + 1;
		write(getmn(x, y));
	}
	return 0;
}}
bool End;
il void Usd() {cerr << "\nUse: " << (&Beg - &End) / 1024.0 / 1024.0 << "MB " << (double)clock() * 1000.0 / CLOCKS_PER_SEC << "ms\n";}
signed main() {
	Zctf1088::main();
	Usd();
	return 0;
}

费用流

概述

给定网络 \(G\)，每条边上除了有容量限制 \(c(u,v)\)，还有一个单位流量的费用 \(w(u,v)\)。即当一条边的流量为 \(f(u,v)\) 时，需要花费 \(f(u,v) \times w(u,v)\) 的代价。

费用流的问题即为：在满足最大流的情况下，求最大/小费用，称最大/小费用最大流问题。二者便统称为费用流问题。

板子题：

P3381 【模板】最小费用最大流

给定网络 \(G\)，求其最小费用最大流。

SPFA 费用流

posted @ 2026-01-10 18:29 Zctf1088 阅读(13) 评论(0) 收藏举报

刷新页面返回顶部

Zctf1088

路虽远，行则将至。

网络流

网络流

概念

最大流

FF 算法

EK 算法

Dinic 算法

最小割

定义

最大流最小割定理

内容

证明

引理 1

引理 2

最小割树

费用流

概述

SPFA 费用流

公告