介绍
网络流解决的是建模出来的流量网络的一些问题。
一个流量网络中，会有一个源点和一个汇点。网络中的每一条边都有一个边权，为容量。
想象每条边都是有流量限制的水管，水从源点源源不断地流入，再从汇点源源不断地流出。在这个过程中，每条水管中的流量限制都不能其限制。
由此，衍生出了一些问题，比如汇点最大流量是多少，这就是最大流问题。
最大流算法实现
主流的最大流算法分两个大类，增广路算法和预推流算法。
- 增广路：EK,dinic,SAP,ISAP
- 预推流：Push-Relabel,HLPP
只写了dini模板，其它有时间再补吧。
增广路
增广路就是，如果存在一条从源点到汇点的路，路上边剩余容量都不为0，那么就可以对这条路进行增广操作。
增广路算法基本上就是从源点到汇点不停找增广路，直到找不到为止。累计下来的流量就是最大流。
EK： dfs暴力找。
dinic：每次dfs增广之前bfs一次给图分层，提高效率。
SAP：用一个num数组来记录分层信息，dfs同时更新num，不用bfs那么多次。
ISAP：相比SAP多一个gap优化。
两个优化方向
- cur当前弧优化。一次dfs中一个边被增广过后就不会再被增广，所以用cur保存最后一次的边。（详见代码）
- 多路增广。如果当前结点流量没流完，那就走多几条路尽可能流完它。
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const double eps = 1e5;
struct edge {
int ne, np, f;
};
edge ed[M];
int head[N];
int cur[N];
int si = 2;
int dis[N];
int arr[N];
ll cost[N];
void init() {
si = 2;
memset(head, 0, sizeof head);
memset(cur, 0, sizeof cur);
}
void add(int u, int v, int f) {
ed[si] = edge{head[u], v, f};
head[u] = si;
cur[u] = head[u];
si++;
ed[si] = edge{head[v], u, 0};
head[v] = si;
cur[v] = head[v];
si++;
}
bool bfs(int s, int t) {
memset(dis, 0, sizeof dis);
for(int i = 1; i <= t; i++) cur[i] = head[i]; // 当前弧优化，注意这里初始化是所有的点初始化
queue<int> q;
q.push(s);
dis[s] = 1;
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int i = head[cur]; i; i = ed[i].ne) {
int nt = ed[i].np;
if(dis[nt] || (!ed[i].f)) continue;
dis[nt] = dis[cur] + 1;
q.push(nt);
}
}
return dis[t];
}
int dfs(int p, int t, int flo) {
if(p == t) return flo;
int delta = flo;
for(int &i = cur[p]; i; i = ed[i].ne) {
int nt = ed[i].np;
if(dis[nt] == dis[p] + 1 && ed[i].f) {
int d = dfs(nt, t, min(delta, ed[i].f));
delta -= d;
ed[i].f -= d; ed[i^1].f += d;
if(delta == 0) break;
}
}
return flo - delta;
}
ll dini(int s, int t) {
ll ans = 0;
while(bfs(s, t)) {
ans += dfs(s, t, INF);
}
return ans;
}
预推流
本人菜+没时间，以后再补qwq
一些小要点
- 最大流算法的反向边实现了反悔的操作。
- 可以用拆点的方法添加满足题目的一些限制条件，或代表点的限制。
- 添加一些点和边构建适应不同要求的模型，如有最小流限制等。
最小割
最小割是最大流的镜像问题。
最小割即对一个流量网络，割掉一些边，使得从源点到不了汇点。问割掉的边最小的容量和是多少。
事实上，最小割=最大流。
通过这个事实，我们可以互相地证明增广路算法的正确性。
记一个书上的证明