前言
网络流更多的是考验建模能力，将图建出来后几乎就变成模版了
思路
先介绍一下什么是最大流和网络流的基础概念。
最大流
网络流在有向有权图（注意不一定是一个DAG）上跑的一个算法。通常有一个源点 和一个汇点 。我们先介绍最大流问题。
什么是最大流？可以理解成有一个自来水公司从 往之后可以到达的点送水，初始有无限多的水，问最多能有多少点到达汇点 。这时候可能就要问了，水不是无限多的吗？注意有权图。我们刚才只考虑了有向。每条边都是水管，权值是一个上限，最多有这么多的水可以经过这条管道。可以理解为不同的管道宽度不一样，最多有这么多的水可以流过去。
比如这张图，如果我想从 流到 能有多少水可以到呢？ 说 或 的就错了。由于最多有 个单位的水可以流到 ，所以 流到 也就只有 了。
这个图的最大流就是 和 与 ，加起来等于 ，但是该咋算呢？
Edmond-Karp（EK）
首先第一反应是什么，贪心找最大然后去找路径。但是这个不对。这个感觉跟贪心不适用于DP一样，有可能前面有一个权值为 的边（就是假设），之后等走到了又有一个唯一的权值为 的边，这就不对了。因为加的权值是路径上长度最小的边，由于涉及到全图，所以有局部性的贪心就不行了（至少是上面那个思路）。
最大流是什么，多个路径让能到 的水增加。那我们找出来这些路径不就行了吗。我们引出一个增广路 的概念。
从 到 的一条路径，可以让 的值增加。
那么，我们找出增广路就是找最大流，但是现在可能一头雾水，感觉很不对劲。先讲吧。
怎么找增广路？广搜即可，找出来一条路径然后记录。路径的边权要大于 （之后会减边权）。
bool bfs() {
memset(inq, false, sizeof(inq));
queue<ll> q;
inq[s] = true;
q.push(s);
while (!q.empty()) {
ll u = q.front();
q.pop();
for (ll i = head[u]; i; i = e[i].nxt) {
ll v = e[i].to, w = e[i].weight;
if (!inq[v] && w != 0) {
pre[v].last = u;
pre[v].edge = i;
if (v == t) {
return true;
}
inq[v] = true;
q.push(v);
}
}
}
return false;
}
之后如果不作出改变的话不就死循环了吗？我们要把这条路径的所有值都减去这个路径的最小权值。这个的意思就是已经有这么多的水流过去了，不可以一直流过去。之后答案加上最小值即可。诶嘿是不是很简单。好的做完了。是对的原因是如果是有增广路的话那么就是能走的路还有边权不是 的，之后结束就是该流的都流完了。
但是！
我们的路径完全没有顺序关系，如果我之前可以走一个更好的路径，但是这个路径上的权值已经被改变的很小了，那么就不是最大流了。有一个技巧是加反向边。在减边权的时候把反向边加上那个边权。之后正常遍历。就对了。因为反向边记录的是之前走的人，由于是试错，之前走了这么多的人可以再返回走新的一条道。最后不能走的情况就是都正确的到达了 点了。结束😆
代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const ll INF = ll(1e30);
ll read() {
ll a = 0, w = 1;
char c = getchar();
while (!(c >= '0' && c <= '9')) {
if (c == '-') { w = -1; }
c = getchar();
}
while (c >= '0' && c <= '9') {
a = (a << 3) + (a << 1) + (c ^ 48);
c = getchar();
}
return w * a;
}
void write(ll num = '\n') {
if (num == '\n') {
putchar('\n');
return;
}
if (num < 0) {
putchar('-');
num = -num;
}
if (num > 9) { write(num / 10); }
putchar((num % 10) + '0');
}
const ll MAXN = 200 + 5;
const ll MAXM = 10000 + 5;
ll n, m, s, t;
struct edge {
ll to, weight, nxt;
} e[MAXM];
ll head[MAXN], tot = 1;
void add(ll u, ll v, ll w) {
e[++tot].nxt = head[u];
e[tot].to = v;
e[tot].weight = w;
head[u] = tot;
}
struct node {
ll last, edge;
} pre[MAXN];
bool inq[MAXN];
bool bfs() {
memset(inq, false, sizeof(inq));
queue<ll> q;
inq[s] = true;
q.push(s);
while (!q.empty()) {
ll u = q.front();
q.pop();
for (ll i = head[u]; i; i = e[i].nxt) {
ll v = e[i].to, w = e[i].weight;
if (!inq[v] && w != 0) {
pre[v].last = u;
pre[v].edge = i;
if (v == t) {
return true;
}
inq[v] = true;
q.push(v);
}
}
}
return false;
}
ll ek() {
ll ans = 0;
while (bfs()) {
ll Min = INF;
for (ll i = t; i != s; i = pre[i].last) {
Min = min(Min, e[pre[i].edge].weight);
}
ans += Min;
for (ll i = t; i != s; i = pre[i].last) {
e[pre[i].edge].weight -= Min;
e[pre[i].edge ^ 1].weight += Min;
}
return ans;
}
int main() {
n = read();
m = read();
s = read();
t = read();
for (int i = 1; i <= m; ++i) {
ll u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, 0);
}
write(ek());
return 0;
}
时间复杂度
这个算法的时间复杂度为 ，就是不断遍历边然后每一次遍历就要遍历一遍图。
Dinic
在 EK 算法中，我们每做一次 bfs 都只能找出一条增广路来，这是不是有点浪费算力了。我们能不能通过一次遍历找出很多条最短路来？
大体思路
在 EK 算法中，每一次 bfs 就好像只有一个小人在跑，而如果想要找出多条增广路就需要让很多个小人同时跑，每一个都要找出一条增广路，是不是一下就感觉快了呢？
我们思考一下学过的所有算法，是不是dfs 符合这个性质呢？
我们之后每一次都跑一遍 dfs，然后之前用 bfs 确定是否还有增广路。
优化
首先，我们可以把这张图按照 bfs 序分层，这样每一条路径就在同层中取一个点再往下递归就行了，这样不会出现来回走来回走之后发现错了再回溯然后费死劲的情况了。（好像有点皮）
之后我们发现，如果在这个点递归后的值为 ，就说明这个点丝毫没有意义，可以直接剪枝，在这次 dfs 中就不再走这个点了。
之后就是 弧优化，如果之前已经走过了这条边，就说明这个边和之后的增广路已经找到了，就不用再次遍历一遍了。
代码
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
const ll MAXN = 200 + 5;
const ll MAXM = 5000 + 5;
const ll INF = ll(1e30);
ll n, m, s, t;
struct edge {
ll to, weight, nxt;
} e[MAXM * 2];
ll head[MAXN], tot = 1;
void add(ll u, ll v, ll w) {
e[++tot].nxt = head[u];
e[tot].to = v;
e[tot].weight = w;
head[u] = tot;
}
ll dep[MAXN], arc[MAXM * 2];
bool bfs() {
for (int i = 0; i < MAXN; ++i) {
dep[i] = -1;
}
queue<ll> q;
q.push(s);
dep[s] = 0;
while (!q.empty()) {
ll u = q.front();
q.pop();
for (ll i = head[u]; i; i = e[i].nxt) {
ll v = e[i].to, w = e[i].weight;
if (dep[v] == -1 && w) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
if (dep[t] != -1) {
return true;
}
return false;
}
ll dfs(ll u, ll inflow) {
if (u == t) {
return inflow;
}
ll outflow = 0;
for (ll i = arc[u]; i && inflow; i = e[i].nxt) {
arc[u] = e[i].to;
if (dep[e[i].to] == dep[u] + 1 && e[i].weight) {
ll v = e[i].to, W = dfs(v, min(e[i].weight, inflow));
if (W == 0) {
dep[v] = -INF;
}
e[i].weight -= W;
e[i ^ 1].weight += W;
outflow += W;
inflow -= W;
}
}
return outflow;
}
ll dinic() {
ll ans = 0;
while (bfs()) {
for (int i = 1; i <= n; ++i) {
arc[i] = head[i];
}
ans += dfs(s, INF);
}
return ans;
}
int main() {
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
for (int i = 1; i <= m; ++i) {
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
add(u, v, w);
add(v, u, 0);
}
printf("%lld\n", dinic());
return 0;
}
时间复杂度
理论上的时间复杂度是 的，但是如果加上了上面的三个剪枝，时间复杂度将超级大幅度的降低。所以虽然理论上时间复杂度EK 和 Dinic 差不多，但是实际上 Dinic 会比 EK 好一些。
总结
归纳了最大流的EK和Dinic算法，介绍了网络流是什么。同时对开始的想法进行了优化。
