-
网络流的一些定义和性质
1.流网络（Flow Network）
流网络为一个有向图\(G = (V, E)\)，所有边\((u, v) \in E\) 都有一个容量（Capacity），用\(c(u, v)\)表示。另外规定了两个点：源点（Source）、汇点（Sink），分别为\(s\)和\(t \quad (s \neq t)\)
2.流
-
定义流量为\(f(u, v)\) 为 \(V \times V \rightarrow R\)的函数，表示经过\((u, v)\)这条边的流量。
-
\(c_f(u, v) \ = \ c(u, v) - f(u, v)\)称为边\((u, v)\)的剩余容量。
-
整个网络的流量为\(|f| \ = \ \sum_{(s, v) \in E}f(s, v) \ = \ \sum_{(u, t) \in E} f(u, t)\)
3.流量函数满足的性质：
-
容量限制： 流经某一条边的流量不得超过其容量，即：\(f(u, v) \leq c(u, v)\)
-
流量守恒: 对于除了源点汇点的任意节点 \(x\)，满足： \(\sum_{u \in V} f(u, x) \ = \ \sum_{v \in V} f(x, v)\)
-
斜对称性：每条边流量与其反向边流量之和为0，即：\(f(u, v) + f(v, u) = 0\)
-
最大流
1.描述
对于给定的流网络，要求求出一个流\(f\)，使得\(|f| \ = \ \sum_{(s, v) \in E}f(s, v) \ = \ \sum_{(u, t) \in E} f(u, t)\)最大。
2.几个定义
-
残量网络（Residual Network）： 图\(G\)中所有剩余容量大于0的边构成的子图称为残量网络，用\(G_f\)表示。
-
增广路（Augmenting Path）： \(G_f\)上一条从源点\(s\)到汇点\(t\)的路径称为增广路。
3.Edmonds–Karp 算法
Ford–Fulkerson 增广： 是一种通过寻找增广路求解最大流的方法，步骤如下：
-
1.寻找一条增广路，边集为\(E_a\)。
-
2.令\(f_m \ = \ max \{c_f(u, v) \} \quad (\ (u, v) \ \in E_a \ )\)，对于每一条边\((u, v) \in E_a\)，将 \(f(u, v) \ += \ f_m\)，同时根据斜对称性，将 $f(v, u) \ -= \ f_m $。
-
3.再次建立残量网络，重复1步骤，直至找不到增广路。
Edmonds–Karp 算法即按照上面Ford–Fulkerson 增广的步骤，使用BFS寻找增广路。算法的时间复杂度为\(O(|V| \cdot |E|^2)\)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 20010;
const int M = 200010;
int nextt[M], head[N], to[M], cnt = 1;
int n, m, tot = 0, s, t;
lld w[M];
bool vis[N];
void add(int x, int y, lld z) {
nextt[++cnt] = head[x]; to[cnt] = y;
w[cnt] = z; head[x] = cnt;
}
int edge[N], nxt[N];
bool bfs() {
queue <int> q;
memset(vis, false, sizeof(vis));
q.push(s); vis[s] = true; tot = 0;
memset(edge, 0 ,sizeof(edge)); memset(nxt, 0, sizeof(nxt));
while(!q.empty()) {
int u = q.front(); q.pop();
if(u == t) return true;
for(int i = head[u]; i; i = nextt[i]) {
int v = to[i];
if(w[i] > 0 && !vis[v]) {
q.push(v);
edge[v] = i; nxt[v] = u;
if(!vis[v]) vis[v] = true;
}
}
}
return false;
}
lld EK() {
lld ans = 0;
while(bfs()) {
memset(vis, 0, sizeof(vis)); tot = 0;
lld wi = 1e10;
for(int i = t; i != s; i = nxt[i]) wi = min(wi, w[edge[i]]);
for(int i = t; i != s; i = nxt[i])
w[edge[i]] -= wi, w[edge[i] ^ 1] += wi;
ans += wi;
}
return ans;
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d%d%d%d", &n, &m, &s, &t);
for(int i = 1, u, v; i <= m; i++) {
lld w; cin >> u >> v >> w;
add(u, v, w); add(v, u, 0);
}
cout << EK() << endl;
return 0;
}
4.Dinic 算法
两个定义：
-
层次图（Level Graph）: 对\(G_f\)进行BFS分层，从源点出发经过的边数相同的点为同一层，记\(d(u)\)为节点\(u\)的层数。分层之后保留到达下一层的边，删除同层之间的边从而得到层次图\(G_L\)，即：\(G_L = (V, E_L) \quad E_L = \{ (u, v) \ | \ (u, v) \in E_f, d(v) = d(u) + 1 \}\)
-
阻塞流（Blocking Flow）: 在\(G_L\)找到一个流\(f_b\)，使得\(G_L\)无法继续增广，则称\(f_b\)为\(G_L\)的阻塞流。
Dinic 算法过程：
-
1.在\(G_f\)上进行BFS求出层次图\(G_L\)。
-
2.在\(G_L\)上求出一个阻塞流\(f_b\)。
-
3.将阻塞流\(f_b\)加入到流 \(f\)中，更新残量网络\(G_f\)。
-
4.重复执行1，2，3过程，直到无法找到阻塞流（层次图中\(s\)到\(t\)不连通）
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 10005;
const int M = 200005;
int nextt[M], head[N], to[M];
lld w[M];
int n, m, s, t, cnt = 1;
int dis[N], cur[N];
void add(int x, int y, lld z) {
nextt[++cnt] = head[x]; w[cnt] = z;
to[cnt] = y; head[x] = cnt;
}
bool bfs() {
queue <int> q;
memset(dis, 0, sizeof(dis));
q.push(s); dis[s] = 1;
bool flag = false;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; i; i = nextt[i]) {
int v = to[i];
if(w[i] > 0 && !dis[v]) {
dis[v] = dis[u] + 1; q.push(v);
if(v == t) flag = true;
}
}
}
return flag;
}
lld dfs(int u, lld mine) {
lld minedge = 0;
if(u == t) return mine;
for(int i = cur[u]; i; i = nextt[i]) {
int v = to[i]; cur[u] = i;
if(w[i] > 0 && dis[v] == dis[u] + 1) {
lld now = dfs(v, min(mine, w[i]));
minedge += now;
w[i] -= now; w[i ^ 1] += now;
mine -= now;
if(!mine) break;
}
}
return minedge;
}
void dinic() {
lld ans = 0;
while(bfs()) {
memcpy(cur, head, sizeof(head));
ans += dfs(s, 1e10);
}
cout << ans << endl;
}
int main() {
// freopen("data.in", "r", stdin);
cin >> n >> m >> s >> t;
for(int i = 1, u, v; i <= m; i++) {
lld z; cin >> u >> v >> z;
add(u, v, z); add(v, u, 0);
}
dinic();
return 0;
}
当前弧优化： DFS时，每次增广完一条路径\((u, v)\)之后，\((u, v)\)的容量所剩无几，下一次到达\(u\)时直接选择跳过\((u, v)\)，从下一条边开始增广。在代码中，使用\(cur[u]\)数组记录点\(u\)第一条未使用的边。
-
最小割
1.几个定义
-
割： 又称s-t割，是一种点的划分方式，将所有点分为两个集合\(S\)和\(T\)，其中\(s \in S\)，$t \in T $
-
割的容量： 定义为所有从\(S\)中的点出发到达\(T\)中的点的边的容量之和，即：\(c(S,T) = \sum_{u \in S, v \in T} c(u, v)\)。
-
最小割： 求出一个割使得\(c(S,T)\) 最小。
2.最大流最小割定理
在任何网络中，最大流的值等于最小割的容量。
标签：cnt,最大,增广,int,最小,dis,head,lld From： https://www.cnblogs.com/mcggvc/p/17607793.html