「网络流浅谈」最小割的模型

· 浏览次数 : 0

小编点评

**算法简介：** 该算法计算最大权独立集，并通过最小权点覆盖集的求解方法求解最大权独立集。 **关键步骤：** 1. **初始化：** - 创建一个数组 `h`，用于存储每个点的深度，初始值为 -1。 - 创建一个数组 `e`，用于存储每个点的入度。 - 创建一个数组 `ne`，用于存储每个点的出度。 - 创建一个数组 `f`，用于存储每个点的最终状态。 - 初始化一个数组 `idx`，用于记录当前已经访问的节点数量。 - 设置一个变量 `s`，指向要访问的节点。 - 设置一个变量 `t`，指向图的边数。 2. **图搜查：** - 使用深度优先搜索 (DFS) 遍历图，标记已访问的节点。 - 对于每个未被访问的节点，设置其深度为 `d[u]` 的值。 - 扩展到所有与当前节点相邻的节点，并更新其深度和父节点。 - 如果当前节点已成为 `t`，则表示找到最大权独立集。 3. **最小权点覆盖集：** - 在搜索过程中，记录每个节点的入度。 - 对于每个入度为 1 的节点，将其加入最小权点覆盖集。 - 计算最小权点覆盖集的总和。 4. **结果输出：** - 输出最小权点覆盖集的总和。 **代码：** ```c++ signed main() { // ... // DFS 遍历图，计算深度和父节点 dfs(s); // 计算最小权点覆盖集 int flow = find(s, 1e18); // 输出结果 cout << tot - dinic() << endl; return 0; } ``` **注意：** - `dinic()` 函数使用深度优先搜索和动态规划来计算最大权独立集。 - `find()` 函数使用深度优先搜索来寻找最小权点覆盖集。 - `dfs()` 函数用于执行深度优先搜索。

正文

最大权闭合子图

引入 Introduction

闭合子图指对于子图 \(G=(V,E)\)，\(\forall u \in V, (u,v)\in E\)，都有 \(v\in V\)。

最大权闭合子图无非就是对于所有的闭合子图 \(G\) 中 \(\sum_{u\in V} w_u\) 最大的闭合子图。

对于这个图中，闭合子图有哪些呢？

红色框圈画出的即为 \(1\) 个闭合子图，因为对于任意一个点所连向的点都在该子图内。

主算法 Main Algorithm

不难发现任意一个割所划分成的 \(2\) 个集合均为闭合子图，而我们要求最大权闭合子图，故考虑如何求解。

建立一个流网络，将源点向所有权值为正的点连一条长度为该点权值的边，将所有权值为负数的点向汇点连一条长度为该点权值的绝对值的边。对于原图中的边，在流网络中均为 \(+\infty\)。

对于割 \([S,T]\)，\(c(S,T)=\sum_{(u,v)\in E,u\in S,v\in T}c(u,v)\)，由于中间的边权均为 \(+\infty\)，所以只会割两边的边，即 \(c(S,T)=\sum_{(s,v)\in E,v\in T}c(s,v)+\sum_{(u,t)\in E,u\in S}c(u,t)\)。

又因为建图的时候 \(s\) 所连向的边，均为连向点的边权；而连向 \(t\) 的边的边权均为连向他点的权值。故，\(c(S,T)=\sum_{(s,v)\in E,v\in T}c(s,v)+\sum_{(u,t)\in E,u\in S}c(u,t)=\sum_{(s,v)\in E,v\in T}w_v-\sum_{(u,t)\in E,u\in S}w_u\)

考虑最大权闭合子图的权值为什么？\(val=\sum_{(s,v)\in E,v\in S}w_v+\sum_{(u,t)\in E,u\in S}w_u\)。

不难发现第二项是完全一样的：所以将 \(c(S,T)\) 与 \(val\) 相加得，\(c(S,T)+val=\sum_{(s,v)\in E,v\in T}w_v+\sum_{(s,v)\in E,v\in S}w_v\)

由于 \(S\) 与 \(T\) 共同构成了点集 \(V\)，故 \(\sum_{(s,v)\in E,v\in T}w_v+\sum_{(s,v)\in E,v\in S}w_v=\sum_{(s,v)\in E}w_v=\sum_{w_v>0}w_v\)

综上所述，\(val=\sum_{w_v>0}w_v-c(S,T)\)，通过数学知识推理得 \(c(S,T)\) 应最小，即求最小割。

P4174 [NOI2006] 最大获利

模版题，按照上述做法建图即可。

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 6e4 + 10, M = 4e5 + 10, INF = 1e18;

int n, m, s, t;
int a[N], b[N];
int h[N], e[M], ne[M], f[M], idx;
int dist[N], cur[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
	memset(dist, -1, sizeof dist);
	queue<int> q;
	q.emplace(s), dist[s] = 0, cur[s] = h[s];
	while (q.size()) {
		auto u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (dist[v] == -1 && f[i]) {
				dist[v] = dist[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
int find(int u, int lim) {
	if (u == t) return lim;

	int flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (dist[v] == dist[u] + 1 && f[i]) {
			int tmp = find(v, min(f[i], lim - flow));
			if (!tmp) dist[v] = -1;
			flow += tmp, f[i] -= tmp, f[i ^ 1] += tmp;
		}
	}

	return flow;
}
int dinic() {
	int res = 0, flow;
	while (bfs()) while (flow = find(s, INF)) res += flow;
	return res;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;
	memset(h, -1, sizeof h);

	s = 0, t = n + m + 1;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= m; i ++) {
		int u, v;
		cin >> u >> v >> b[i];
		add(i + n, u, INF), add(i + n, v, INF);
	}

	int tot = 0;
	for (int i = 1; i <= m; i ++)
		add(s, i + n, b[i]), tot += b[i];
	for (int i = 1; i <= n; i ++)
		add(i, t, a[i]);

	cout << tot - dinic() << endl;

	return 0;
}

最大密度子图

引入 Introduction

定义无向图 \(G=(V,E)\) 的密度为 \(\frac{|E|}{|V|}\)。则，对于一个无向图 \(G=(V,E)\)，令 \(G\) 的子图 \(G'=(V',E')\)，满足 \(\forall (u,v)\in E', u\in V',v\in V'\)。对于所有满足条件的子图 \(G\) 中，密度最大的即为最大密度子图。

主算法 Main Algorithm

对于形式 \(\frac{|E|}{|V|}\)，不难想到通过分数规划求解，即二分 \(g\)，如果 \(\frac{|E|}{|V|}\ge g\)，则说明 \(g\) 还可以更大，调整二分左端点；反之，调整二分右端点。

将式子继续化简可以得到：\(|E|-g|V|\ge 0\)，也就是求 \(|E|-g|V|\) 的最大值，即 \(g|V|-|E|\) 的最小值。

最小割是可以解决点集的，但是难以算出边数的多少。所以，考虑如何将边数加入割。

考虑红色圈出的子图，如何计算边数呢？可以考虑使用度数，某个点度数减去该点连向集合外部的边的个数再除 \(2\)，即可得到集合内边的个数，即 \(\frac{\sum_{u\in V}d_u-c(V,\bar V)}{2}\)。这样，就与割产生了关系。

继续推式子：\(g|V|-|E|=\sum_{u\in V}g-\frac{\sum_{u\in V}d_u-c(V,\bar V)}{2}=\sum_{u\in V}(g-\frac{d_u}{2})+\frac{c(V,\bar V)}{2}\)

为了使与最小割有单调关系，将割 \(c(V,\bar V)\) 的系数提出得 \(\frac{\sum_{u\in V}(2g-d_u)+c(V,\bar V)}{2}\)

那么，就可以建图了。对于任意一个点 \(u\) 均向汇点 \(t\) 连一条边权为 \(2g-d_u\) 的边，不过由于 \(2g-d_u\) 可能会小于 \(0\)，所以边权应为 \(2g-d_u+U\)，其中 \(U\) 为常数。对于点之间的边，即为原图的边，为了算边数所以边权均为 \(1\)。源点 \(s\) 向任意一个点连一条边权为 \(U\) 的边即可。\(U\) 取 \(|E|\) 即可，因为 \(d_u\) 不可能超过 \(|E|\)。下图为一个例子。

建完图后，由于部分边权多加了 \(U\)，所以考虑新图最小割 \(c'(S,T)\) 与 \(|E|-g|V|\) 的关系。令 \(P=S-\{s\},P'=\bar P - \{t\}\)，则最小割的边集分为 \(4\) 种情况：\(P\rightarrow \{t\},\{s\}\rightarrow P',P\rightarrow P',\{s\}\rightarrow \{t\}\)。不过，最后一种边不存在舍去。

\[\begin{aligned} c'(S,T)=&\sum_{u\in P} (U+2g-d_u)+\sum_{v\in P'}U+\sum_{u\in P}\sum_{v\in P'}c(u,v)\\ =&\sum_{u\in P}(U+2g-d_u+\sum_{v\in P'}c(u,v))+\sum_{v\in P'}U\\ =&\sum_{u\in P}(U+2g-(d_u-\sum_{v\in P'}c(u,v)))+\sum_{v\in P'}U\\ =&\sum_{u\in P}(U+2g-\sum_{v\in P}c(u,v))+\sum_{v\in P'}U\leftarrow u\ 所有出边-向集合外边=向集合内边\\ =&\sum_{u\in P}2g-\sum_{u\in P}\sum_{v\in P}c(u,v)+\sum_{v\in P'}U+\sum_{v\in P}U\\ =&|P|2g+ 2|E|+U\cdot n\\ \end{aligned} \]

故，\(|E|-g|V|=\frac{U\cdot n-c'(S,T)}{2}\)，这里 \(V\) 与 \(P\) 等价，都是我们选出的点。到此，该问题得以解决。

POJ3155 - Hard Life

模版题，使用上述做法建图计算即可。

对于输出方案，选择的集合其实就是最小割中 \(S\) 集合，那么怎么找出呢？只需要从 \(s\) 每次走 \(>0\) 的边所能到达的点的集合，便是答案（注意：不能包含 \(s\)）。

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e2 + 10, M = 3e3 + 10;
const double eps = 1e-6;

int n, m, s, t;
int h[N], e[M], ne[M], idx;
double f[M];
int d[N], cur[N], dg[N], st[N];
vector<int> res;
std::vector<PII> E;

void add(int a, int b, double c1, double c2) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c1, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = c2, h[b] = idx ++;
}
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), d[s] = 0, cur[s] = h[s];
	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (d[v] == -1 && f[i] > 0) {
				d[v] = d[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
double find(int u, double lim) {
	if (u == t) return lim;

	double flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (d[v] == d[u] + 1 && f[i] > 0) {
			double tmp = find(v, min(lim - flow, f[i]));
			if (tmp <= 0) d[v] = -1;
			f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
		}
	}

	return flow;
}
void build(double g) {
	memset(h, -1, sizeof h);
	idx = 0;
	for (auto v : E) add(v.fi, v.se, 1, 1);
	for (int i = 1; i <= n; i ++) add(s, i, m, 0);
	for (int i = 1; i <= n; i ++) add(i, t, 2.0 * g - dg[i] + m, 0);
}
bool dinic(double g) {
	build(g);
	double res = 0, flow;
	while (bfs()) while (flow = find(s, 1e18)) res += flow;
	return res < m * n * 1.0;
}
void dfs(int u) {
	if (u != s) res.emplace_back(u);
	st[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!st[v] && f[i] > 0) dfs(v);
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	s = 0, t = n + 1;
	for (int i = 1; i <= m; i ++) {
		int u, v;
		cin >> u >> v;
		E.emplace_back(u, v), dg[u] ++, dg[v] ++;
	}

	double l = 0, r = m;
	while (r - l > eps) {
		double mid = (l + r) * 0.5;
		if (dinic(mid)) l = mid;
		else r = mid;
	}

	dinic(l), dfs(s);
	if (!res.size()) {
		cout << "1\n1";
		return 0;
	}
	cout << res.size() << endl;
	sort(res.begin(), res.end());
	for (auto v : res)
		cout << v << endl;
	cout << endl;

	return 0;
}

最小权点覆盖集

引入 Introduction

点覆盖集指选择点集 \(V\)，使得对于边集 \(E\) 中的每一条边，至少有一个端点在点集 \(V\) 中。

最小权点覆盖集指在所有点覆盖集中，点的权值和最小的点集。

主算法 Main Algorithm

最小权点覆盖集只有在二分图的情况下才存在高效解，否则为 NPC 问题。

考虑如何将点覆盖集与割建立联系。对于一个点，如果割集中存在，那么说明点覆盖集中选择该点，同时在原图中与该点相连的点应不被割才符合题意，否则该边不存在任何点覆盖。

所以，网络流中的原图的边不能被割掉，故边权均为正无穷。不过，点是可以被割掉的，所以源点流向二分图一侧的每一个点，边权为该点的权值。从二分图的另一侧流向汇点，边权为该点的权值。（下图为示例）

不难发现，这样建立边权与原问题是等价的。考虑反证法，若存在一条边 \((u,v)\)，点 \(u\) 和点 \(v\) 都没有被选择，那么说明源点连向 \(u\) 的边与 \(v\) 连向汇点的边均未被割，这说明残留网络中必然存在增广路（因为网络流中的 \((u,v)\) 边权为正无穷），与假设矛盾，证毕。

所以，在该网络流上跑最小割，即可求出原二分图的最小点全覆盖集。

代码 Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 点数, M = 边数;

int n, m, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N], st[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), d[s] = 0, cur[s] = h[s];
	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (d[v] == -1 && f[i]) {
				d[v] = d[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
int find(int u, int lim) {
	if (u == t) return lim;

	int flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (d[v] == d[u] + 1 && f[i]) {
			int tmp = find(v, min(lim - flow, f[i]));
			if (!tmp) d[v] = -1;
			f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
		}
	}
	return flow;
}
int dinic() {
	int res = 0, flow;
	while (bfs()) while (flow = find(s, 1e18)) res += flow;
	return res;
}
void dfs(int u) {
	st[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!st[v] && f[i]) dfs(v);
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);
	cin >> n >> m;

	s = 0, t = 2 * n + 1;
	int w;
	for (int i = 1; i <= n; i ++)
		cin >> w, add(s, i, w);
	for (int i = n + 1; i <= n * 2; i ++)
		cin >> w, add(i, t, w);
	while (m -- ) {
		int a, b;
		cin >> a >> b;
		add(a, b + n, 1e18);
	}

	cout << dinic() << endl;
    
    return 0;
}

习题

POJ2125 - Destroying The Graph

最大权独立集

引入 Introduction

独立集指对于图 \(G(V,E)\)，选出点集 \(V'\)，使得对于 \(V'\) 中的任意 \(2\) 个点，\(2\) 点间都不存在一条边。

最大权独立集指对于所有独立集中点的权值和最大的独立集为最大权独立集。

主算法 Main Algorithm

最大权独立集 = 所有点权和 - 最小权点覆盖集

证明：

对于任意的点覆盖集 \(V_1\)，\(V_1\) 在 \(V\) 中的补集 \(V_2\) 恒为独立集。

证明：反证法。若不是独立集，说明存在边 \((u,v)\) 使得 \(u,v\in V_2\)，那么由于 \(V_2\) 为 \(V_1\) 的补集，所以 \(u,v\not\in V_1\)，故 \(V_1\) 不是点覆盖集。与假设矛盾，证毕。

所以，\(\sum_{i\in V_1}w_i+\sum_{i\in V_2}w_i=\sum_{i=1}^n w_i\)。

故，当前项（最小权点覆盖集）取最小时，后项（最大权独立集）取最大。

综上所述，只需要沿用最小权点覆盖集的求解方法，并用总和减去其权值即可。

代码 Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 点数, M = 边数;

int n, m, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N], st[N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
	e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx ++;
}
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), d[s] = 0, cur[s] = h[s];
	while (q.size()) {
		int u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int v = e[i];
			if (d[v] == -1 && f[i]) {
				d[v] = d[u] + 1, cur[v] = h[v];
				if (v == t) return 1;
				q.emplace(v);
			}
		}
	}
	return 0;
}
int find(int u, int lim) {
	if (u == t) return lim;

	int flow = 0;
	for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (d[v] == d[u] + 1 && f[i]) {
			int tmp = find(v, min(lim - flow, f[i]));
			if (!tmp) d[v] = -1;
			f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
		}
	}
	return flow;
}
int dinic() {
	int res = 0, flow;
	while (bfs()) while (flow = find(s, 1e18)) res += flow;
	return res;
}
void dfs(int u) {
	st[u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];
		if (!st[v] && f[i]) dfs(v);
	}
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);
	cin >> n >> m;

	s = 0, t = 2 * n + 1;
	int w, tot = 0;
	for (int i = 1; i <= n; i ++)
		cin >> w, add(s, i, w), tot += w;
	for (int i = n + 1; i <= n * 2; i ++)
		cin >> w, add(i, t, w), tot += w;
	while (m -- ) {
		int a, b;
		cin >> a >> b;
		add(a, b + n, 1e18);
	}

	cout << tot - dinic() << endl;
    
    return 0;
}

习题

  1. P4474 王者之剑
  2. ABC354 G - Select Strings

与「网络流浅谈」最小割的模型相似的内容：

「网络流浅谈」最小割的模型

总结了最小割的四个模型——最大权闭合图，最大密度子图，最小点覆盖集，最大权独立集。带你走进最小割的神秘！

0
「网络流浅谈」最小割的模型 1

最大权闭合子图 引入 闭合子图指对于子图 \(G=(V,E)\)，\(\forall u \in V, (u,v)\in E\)，都有 \(v\in V\)。 最大权闭合子图无非就是对于所有的闭合子图 \(G\) 中 \(\sum_{u\in V} w_u\) 最大的闭合子图。 对于这个图中，闭合子

0
「网络流浅谈」网络流的概念

通常做题思路：问题转化为流网络，再通过最大流 / 最小割 / 费用流与问题之间的数量关系，求解出原问题。 网络流于其他算法不同，概念定理需要熟记于心，否则后面做题会有很大的障碍。 1. 流网络 一个流网络记作 \(G=(V,E)\)，其中 \(V\) 表示点集，\(E\) 表示边集。对于 \(\fo

0
「网络流浅谈」最大流的应用

二分图匹配 考虑如何将二分图匹配问题，转化为流网络。设置 \(1\) 个汇点和源点，从源点向二分图一侧的每一个点连边，从另一侧向汇点连边，边权均为 \(1\)，二分图中的边也全部加入，权值设为 \(1\)。这样，二分图的最大匹配等于流网络的最大流。 P2756 飞行员配对方案问题 题意：给定 \(1

5
浅谈k8s中cni0和docker0的关系和区别

最近在复习k8s网络方面的知识，查看之前学习时整理的笔记和文档还有过往自己总结的博客之后发现一个问题，就是在有关flannel和calico这两个k8s网络插件的文章和博客中，会涉及到cni0和docker0这两个网桥设备，但是都没有明确说明他们俩之间的关系，有的甚至将两者混为一谈，这也是我之前的学

k8s cni0 docker0
0
[转帖]【网络小知识】之TCP IP 五元组(five-tuple/5-tuple)

为什么要分享TCP IP 5元组(five-tuple/5-tuple的知识? 最近在进行深度分析过程中,听到某些资深人士提到了5元组这个概念，觉得很高大尚，去搜索了一圈，发现都是些非常浅显的知识，对于tcp ip 5元组，7元组有什么用没有提及，也没有五元组的英文，导致英文资料检索过程中饶了一圈。

网络 知识 tcp ip
0
500代码行代码手写docker-设置网络命名空间

# (4)500代码行代码手写docker-设置网络命名空间 > 本系列教程主要是为了弄清楚容器化的原理，纸上得来终觉浅，绝知此事要躬行，理论始终不及动手实践来的深刻，所以这个系列会用go语言实现一个类似docker的容器化功能，最终能够容器化的运行一个进程。 本章的源码已经上传到github，地址

代码 手写 docker 设置
213
[转帖]张磊：浅谈容器网络

https://zhuanlan.zhihu.com/p/595014129 你好，我是张磊。今天我和你分享的主题是：浅谈容器网络。 在前面讲解容器基础时，我曾经提到过一个Linux容器能看见的“网络栈”，实际上是被隔离在它自己的Network Namespace当中的。 而所谓“网络栈”，就包括了

浅谈 容器 网络
0
算法学习笔记(8): 网络流

# 网络流 > 网络流是一个博大精深的一个话题…… ## 箕(基)畚(本)知识 文章链接：[基本知识](https://www.cnblogs.com/jeefy/p/17050220.html) ## 网络最大流 文章链接：[网络最大流](https://www.cnblogs.com/jeefy

算法 学习 笔记 网络
44
算法学习笔记(8.0): 网络流前置知识

网络流基础 网络流合集链接：网络流 网络 $G = (V, E)$ 实际上是一张有向图 对于图中每一条有向边 $(x, y) \in E$ 都有一个给定的容量 $c(x, y)$ 特别的，若 $(x,y) \notin E$ , 则 $c(x, y) = 0$ 图中还有两个指定的特殊结点，$S, T

算法 学习 笔记 网络
25
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.