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

· 浏览次数 : 5

小编点评

The provided code aims to find the latest time at which a certain condition is satisfied in a 2D grid. A short explanation below: - The code initializes data structures, including a 2D grid `f` and a list of nodes `pg`. - It uses a breadth-first search (BFS) algorithm to find the latest time that satisfies the condition. - The `find()` function recursively explores the grid, considering all possible paths to find the maximum time that satisfies the condition. - The `add()` function allows for efficient insertion of elements into the grid. - The `solve()` function reads input data and initializes variables for the grid and the search process. - It then iterates through the grid and constructs the list of possible times that satisfy the condition. - Finally, it prints the latest valid time found, or -1 if no such time is found. Here's an example of how the code works: - It starts by reading the dimensions of the grid and the initial conditions. - It then uses a DFS to find the latest time that satisfies the condition. - The output is printed, which would be the latest valid time in the grid. **Additional Notes:** - The `find()` function uses a `d` array to track the minimum number of steps to reach the current position from the starting position. - The `add()` function uses a `d` array to keep track of the minimum distance from the starting position to the current position. - The code assumes that the condition is satisfied when the number of steps from the starting position to the current position is equal to the specified value `ld`.

正文

二分图匹配

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

P2756 飞行员配对方案问题

题意：给定 \(1\) 个二分图，求最大匹配。

匈牙利算法是可以求二分图最大匹配的，不过太慢了。不妨，使用上述的方式建立出流网络，并使用 Dinic 求解出该网络的最大流即可。

举个例子：左图为样例的二分图，而右图为建立的流网络。

浅析流网络最大流与二分图最大匹配的相等性：

对于网络流的题目，只需要考虑对于任意的一个最大匹配，都能对应到一个可行流；而对于任意一个可行流都能对应到一个最大匹配。

对于任意的一个最大匹配，都能对应到一个可行流：若选择边 \(E_1,E_2, \dots ,E_k\)，则可行流中的这些边均为 \(1\)，且令这些边左端的顶点分别为 \(V_1,V_2,\dots,V_t\)，右端的为 \(V'_1,V'_2,\dots, V'_t\)，则可行流的 \(s\rightarrow V_i\) 这些边均为 \(1\)；\(V'_i\rightarrow t\) 这些边也均为 \(1\)。由于匹配不存在 \(2\) 条边有公共顶点，所以一定满足容量限制与流量守恒。

对于任意的一个可行流，都能对应到一个最大匹配：可行流中流量为 \(1\) 的没有 \(s\) 和 \(t\) 的边即为最大匹配，由于流量守恒，最多有 \(1\) 条边流向一个点，所以满足对于任意 \(2\) 条边，都不存在公共点。

故，只需要用 Dinic 跑一遍最大流即可，输出方案就是找出所有反向边流量为 \(1\)（或正向边流量为 \(0\)）的边即可。

注意：二分图下的 Dinic 算法极为特殊，时间复杂度为 \(O(n^2\sqrt n)\)

#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 = 1e5 + 10;

int n, m, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[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(d, -1, sizeof d);
	queue<int> q;
	q.emplace(s), cur[s] = h[s], d[s] = 0;
	while (q.size()) {
		auto u = q.front();
		q.pop();

		for (int i = h[u]; ~i; i = ne[i]) {
			int j = e[i];
			if (d[j] == -1 && f[i]) {
				d[j] = d[u] + 1, cur[j] = h[j];
				if (j == t) return 1;
				q.emplace(j);
			}
		}
	}
	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]) {
		int j = e[i];
		if (d[j] == d[u] + 1 && f[i]) {
			int tmp = find(j, min(lim - flow, f[i]));
			if (!tmp) d[j] = -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;
}

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

	memset(h, -1, sizeof h);

	cin >> m >> n;

	s = 0, t = n + 1;
	int u, v;
	while (cin >> u >> v && u != -1) {
		add(u, v, 1);
	}
	for (int i = 1; i <= m; i ++)
		add(s, i, 1);
	for (int i = m + 1; i <= n; i ++)
		add(i, t, 1);

	cout << dinic() << endl;
	for (int i = 0; i < idx; i += 2)
		if (e[i] != t && e[i ^ 1] != s && !f[i])
			cout << e[i ^ 1] << " " << e[i] << endl;

	return 0;
}

习题

P3254 圆桌问题，与原建图方式有略微差异。

参考代码 
#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 = 5e2 + 10, M = 1e5 + 10;

int m, n, s, t;
int a[N], b[N];
int h[N], e[M], f[M], ne[M], idx;
int d[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(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 j = e[i];
			if (d[j] == -1 && f[i]) {
				d[j] = d[u] + 1;
				cur[j] = h[j];
				if (j == t) return 1;
				q.emplace(j);
			}
		}
	}
	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 j = e[i];
		if (d[j] == d[u] + 1 && f[i]) {
			int tmp = find(j, min(lim - flow, f[i]));
			if (!tmp) d[j] = -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;
}

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

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

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

	if (dinic() == tot) {
		cout << 1 << endl;
		std::vector<vector<int>> way(m + 1);
		for (int i = 0; i < idx; i += 2)
			if (e[i] != t && e[i ^ 1] != s && !f[i])
				way[e[i ^ 1]].emplace_back(e[i] - m);
		for (int i = 1; i <= m; i ++) {
			for (auto v : way[i])
				cout << v << " ";
			cout << endl;
		}
	} else {
		cout << 0 << endl;
	}

	return 0;
}

多源汇最大流

本质上只不过是源点不是 \(1\) 个，汇点也不是 \(1\) 个了，那么其实只需要再设一个超级源点连向所有源点，边权为 \(+\infty\)，表示向这些源点可以流任意多流量，也就是说从这些源点可以流出任意多流量；同样的，从每一个汇点向超级汇点连一条 \(+\infty\) 的边，表示这些汇点可以流向超级汇点任意多流量，也就是说这些汇点都可以接纳任意多的流量。

这样的新流网络的最大流就是源网络的最大流，所以只需要对于新网络跑一遍 Dinic 即可。

习题

AcWing 2234. 多源汇最大流，模版题

参考代码 
#include <iostream>
#include <cstring>
#include <queue>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 5e5 + 10;

int N, M, Sc, Tc, S, T;
int h[SIZE], e[SIZE], ne[SIZE], f[SIZE], idx;
int D[SIZE], Current[SIZE];

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.push(S), D[S] = 0, Current[S] = h[S];
    while (Q.size()) {
        int u = Q.front();
        Q.pop();

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (D[j] == -1 && f[i]) {
                D[j] = D[u] + 1;
                Current[j] = h[j];
                if (j == T) return true;
                Q.push(j);
            }
        }
    }

    return false;
}

int Find(int u, int limit) {
    if (u == T) return limit;

    int flow = 0;
    for (int i = Current[u]; ~i && flow < limit; i = ne[i]) {
        Current[u] = i;
        int j = e[i];
        if (D[j] == D[u] + 1 && f[i]) {
            int T = Find(j, min(f[i], limit - flow));
            if (!T) D[j] = -1;
            f[i] -= T, f[i ^ 1] += T, flow += T;
        }
    }

    return flow;
}

int Dinic() {
    int Result = 0, flow;
    while (BFS()) while (flow = Find(S, 1e18)) Result += flow;
    return Result;
}

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

    memset(h, -1, sizeof h);

    cin >> N >> M >> Sc >> Tc;

    S = 0, T = N + 1;
    while (Sc --) {
        int u;
        cin >> u;
        add(S, u, 1e18);
    }

    while (Tc --) {
        int u;
        cin >> u;
        add(u, T, 1e18);
    }

    while (M --) {
        int a, b, c;

        cin >> a >> b >> c;

        add(a, b, c);
    }

    cout << Dinic() << endl;

    return 0;
}

关键边

POJ3204 Ikki's Story I - Road Reconstruction

题意：给定 \(1\) 个流网络，求有多少条边，满足增加该边边权后能使最大流增加。

考虑一条边满足什么条件使得增加容量后会使得最大流增加，回顾求最大流的过程：每一次在残留网络中找增广路径，并加到最大流中。

那么，如果容量增加后，最大流增加，那么必然是增加流量后产生 \(1\) 条增广路径。所以，对于每一条边 \((u,v)\)，只需要判断是否存在 \(1\) 条增广路径 \(s\rightarrow u\) 以及 \(1\) 增广路径 \(v\rightarrow t\)。判断的方法就是在最大流的残留网络中 DFS，记录每次走 \(>0\) 的边能到达那些点即可。

#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 = 5e2 + 10, M = 2e4 + 10;

int n, m, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N], vis[2][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 j = e[i];
			if (d[j] == -1 && f[i]) {
				d[j] = d[u] + 1, cur[j] = h[j];
				if (j == t) return 1;
				q.emplace(j);
			}
		}
	}
	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 j = e[i];
		if (d[j] == d[u] + 1 && f[i]) {
			int tmp = find(j, min(lim - flow, f[i]));
			if (!tmp) d[j] = -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, int k) {
	vis[k][u] = 1;
	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (!vis[k][j] && f[i ^ k])
			dfs(j, k);
	}
}

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

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

	s = 0, t = n - 1;
	while (m --) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	dinic();
	dfs(s, 0), dfs(t, 1);

	int res = 0;
	for (int i = 0; i < idx; i += 2)
		if (vis[0][e[i ^ 1]] && vis[1][e[i]])
			res ++;

	cout << res << endl;

	return 0;
}

拆点

POJ3281 Dining

题意：有 \(n\) 头奶牛，\(F\) 个食物和 \(D\) 个饮料，每头奶牛可以吃某些食物和饮料，但都只能吃食物和饮料各一个。求最多能满足多少头奶牛。（三分图匹配）

考虑继续使用类似二分图的建网络流的方式，举个例子：

不过，这样真的能够求出最终的答案吗？答案是否定的。

考虑局部的这样一个位置，最大流得到话会流出 \(2\) 的，也就是这个奶牛会贡献 \(2\)，而应该是 \(1\)。

所以，就要拆点了！

通过，流量守恒，就可以使得通过每一个点的流量最多为 \(1\)，也就满足了题意。

#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 = 4e2 + 10, M = 1e5 + 10;

int n, m, k, s, t;
int h[N], e[M], ne[M], f[M], idx;
int d[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(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 j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[u] + 1, cur[j] = h[j];
                if (j == t) return 1;
                q.emplace(j);
            }
        }
    }
    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 j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int tmp = find(j, min(lim - flow, f[i]));
            if (!tmp) d[j] = -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;
}

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

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

    s = 0, t = n * 2 + m + k + 1;
    for (int i = 1; i <= n; i ++) {
        int cf, cd, x;
        cin >> cf >> cd;
        for (int j = 1; j <= cf; j ++)
            cin >> x, add(x, i + m, 1);
        for (int j = 1; j <= cd; j ++)
            cin >> x, add(i + m + n, x + m + n + n, 1);
    }
    for (int i = 1; i <= m; i ++)
        add(s, i, 1);
    for (int i = m + n * 2 + 1; i < t; i ++)
        add(i, t, 1);
    for (int i = m + 1; i <= m + n; i ++)
        add(i, i + n, 1);

    cout << dinic() << endl;

    return 0;
}

习题

P2766 最长不下降子序列问题

参考代码 
#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 = 1e3 + 10, M = 4e5 + 10;

int n, s, t;
int a[N], dp[N];
int h[N], e[M], ne[M], f[M], idx;
int d[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(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 j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[u] + 1, cur[j] = h[j];
                if (j == t) return 1;
                q.emplace(j);
            }
        }
    }
    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 j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int tmp = find(j, min(lim - flow, f[i]));
            if (!tmp) d[j] = -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;
}

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

    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    s = 0, t = 2 * n + 1;

    for (int i = 1; i <= n; i ++) {
        dp[i] = 1, add(i, i + n, 1);
        std::vector<int> opt;
        for (int j = 1; j < i; j ++)
            if (a[j] <= a[i] && dp[j] + 1 > dp[i])
                opt.clear(), opt.emplace_back(j), dp[i] = dp[j] + 1;
            else if (a[j] <= a[i] && dp[j] + 1 == dp[i])
                opt.emplace_back(j);
        for (auto v : opt)
            add(n + v, i, 1);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++)
        res = max(res, dp[i]);
    cout << res << endl;

    for (int i = 1; i <= n; i ++) {
        if (dp[i] == res)
            add(i + n, t, 1);
        if (dp[i] == 1)
            add(s, i, 1);
    }
    res = dinic();
    cout << res << endl;

    for (int i = 0; i < idx; i += 2) {
        if (e[i ^ 1] == 1 && e[i] == 1 + n || e[i ^ 1] == 1 + n && e[i] == t || e[i ^ 1] == s && e[i] == 1)
            f[i] = 1e18;
        else if (e[i ^ 1] == n && e[i] == n + n || e[i ^ 1] == n + n && e[i] == t || e[i ^ 1] == s && e[i] == n)
            f[i] = 1e18;
    }
    res += dinic();
    cout << min(res, n) << endl;

    return 0;
}

POJ3498 March of the Penguins

参考代码 
#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 = 2e2 + 10, M = 2e4 + 10;

int n, s, t;
double ld;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N];
struct Node {
    int x, y;
    int tot, cnt;
    double operator- (const Node &tmp)const {
        int a = x - tmp.x, b = y - tmp.y;
        return sqrt(a * a * 1.0 + b * b * 1.0);
    }
}pg[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 j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[u] + 1, cur[j] = h[j];
                if (j == t) return 1;
                q.emplace(j);
            }
        }
    }
    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 j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int tmp = find(j, min(lim - flow, f[i]));
            if (!tmp) d[j] = -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 solve() {
    cin >> n >> ld;

    int sum = 0;
    for (int i = 1; i <= n; i ++)
        cin >> pg[i].x >> pg[i].y >> pg[i].tot >> pg[i].cnt, sum += pg[i].tot;

    s = 0;
    std::vector<int> res;
    for (t = 1; t <= n; t ++) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= n; i ++) {
            add(s, i, pg[i].tot), add(i, i + n, pg[i].cnt);
            for (int j = 1; j <= n; j ++)
                if (i != j && pg[j] - pg[i] <= ld)
                    add(i + n, j, 1e18);
        }
        if (dinic() == sum)
            res.emplace_back(t);
    }

    if (res.empty())
        cout << -1 << endl;
    else {
        for (auto v : res)
            cout << v - 1 << " ";
        cout << endl;
    }
}

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

    int dt;

    cin >> dt;

    while (dt --)
        solve();

    return 0;
}

与「网络流浅谈」最大流的应用相似的内容：

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

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

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

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

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

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

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

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

0
浅谈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.