当前位置：首页 > news >正文

网络流的一些简略笔记

news 2025/10/27 19:14:04

网络流的一些简略笔记

因为内容太多，写不动博客了，故只在这里记录一下一些小笔记

待补

马上退役了估计也学不了更往后的了大概率考场上也不会见到了从学习算法更多的要转为刷思维了

概念

\(c\) 为容量，\(f\) 为流量，代入类似水管的现实情境感性理解

\(f\) 的性质：

流量不超过容量，\(f<c\)
斜对称，\(f(x,y)=-f(y,x)\)
流量守恒，除源汇点外，所有点流入和流出的流量相同

残量网络：网络中所有节点以及剩余容量大于 \(0\) 的边构成的子图被称为残量网络

割：若网络中的一个边集被删去后，源点和汇点不再联通，则称该边集为网络的割。其大小为边集的容量之和

最大流最小割定理

网络的最大流量等于割的最小流量

证明暂略

通过最大流最小割定理可得出：如果一个流的残量网络上源点和汇点不联通，则这个可行流为最大流。

最大流

EK 算法和 Dinic 算法都为以增广路为核心的最大流算法。

EK 算法

通过多次在残量网络上 bfs 并更新流量，得到最大流

时间复杂度为 \(O(nm^2)\)

void bfs() {queue <int> q;mst(f, -1); f[s] = inf;q.push(s);while(q.size()) {int t = q.front(); q.pop();for(int i = hd[t]; i; i = nxt[i]) {int y = ver[i];if(val[i] > 0 && f[y] == -1) {f[y] = min(f[t], val[i]);pre[y] = i;q.push(y);}}}
}
int maxflow() {ll fl = 0;while(1) {bfs();if(f[t] == -1) return fl;fl += f[t];int p = t;while(p != s) {int i = pre[p];val[i] -= f[t];val[i^1] += f[t];p = ver[i^1];}}
}
void solve() {n = read(), m = read(), s = read(), t = read(), idx = 1;for(int i = 1; i <= m; i++) {int x = read(), y = read(), w = read();add(x, y, w); add(y, x, 0);}write(maxflow());
}

Dinic 算法

对于每条边的前后两点类似深度关系，在残量网络建立分层图，并对相邻层进行增广

并运用了当前弧优化和跳过增广过的边来优化时间

复杂度为 \(O(n^2m)\)，大部分最大流题都不会卡

void bfs() {mst(d, -1);queue <int> q;q.push(s); d[s] = 1, now[s] = hd[s];while(q.size()) {int x = q.front(); q.pop();for(int i = hd[x]; i; i = nxt[i]) {int y = ver[i];if(val[i] > 0 && d[y] == -1) {d[y] = d[x]+1, now[y] = hd[y];q.push(y);if(y == t) return;}}}
}
int dfs(int x, int fl) {if(x == t) return fl;int resf = 0;for(int i = now[x]; i && fl; i = nxt[i]) { // ** i && fl **now[x] = i;int y = ver[i], c = min(fl, val[i]);if(d[y] == d[x]+1 && c > 0) {int k = dfs(y, c);resf += k, fl -= k;val[i] -= k, val[i^1] += k;}}if(resf == 0) d[x] = -1;return resf;
}
int maxflow() {int maxfl = 0;while(1) {bfs();if(d[t] == -1) return maxfl;maxfl += dfs(s, inf);}
}

费用流

即最小费用最大流，每条边上有权值 \(w\)，费用即为 \(f\times w\)。

SSP 算法

通过每次找到长度最短的增广路实现。只能在无负环图上进行。通常基于将 bfs 换为 spfa 的 EK 算法或 Dinic 算法实现。

这里只介绍基于 EK 算法的实现

时间复杂度为 \(O(nmf)\)，\(f\) 为最大流量，但实际上远远达不到

void spfa() {queue <int> q;mst(dis, 0x3f); // 小心因为数据范围挂分mst(mk, 0);f[s] = inf, dis[s] = 0; q.push(s);while(q.size()) {int x = q.front(); q.pop();mk[x] = 0;for(int i = hd[x]; i; i = nxt[i]) {int y = ver[i];if(val[i] && dis[x]+cst[i] < dis[y]) {dis[y] = dis[x]+cst[i];f[y] = min(f[x], val[i]);pre[y] = i;if(!mk[y]) {mk[y] = 1;q.push(y);}} }}
}
pii mincost() {int fl = 0, ct = 0;	while(1) {spfa();if(dis[t] == inf) break;fl += f[t], ct += dis[t]*f[t];int p = t;while(p != s) {int i = pre[p];val[i] -= f[t];val[i^1] += f[t];p = ver[i^1];}}return mp(fl, ct);
}