如何用 vector 实现最大流（题解版）
说明
本文是截至目前为止中文互联网对 vector 实现最大流算法介绍最详细的博客，如果您是初学网络流的 vector 党因为网上对 vector 实现网络流的介绍太少而为难，不妨来看看我的方法。
由于网上已经有很多教程了，所以我对最大流算法的原理不会有特别清楚的介绍，本文着重介绍网上没有教程的如何用 vector 实现最大流。
vector 的局限性
网络流题目中，vector 的局限性主要体现在于：难以实现快速找到反向边。
本文将详细讲解如何消除 vector 的这种局限性。
解决方案
那么 vector 怎么找反向边呢？
我们知道，一条反向边的起点是 st，终点是 ed 的话，按照常规储存方法，我们是这样存图的：
struct edge
{
int ed, len;
}
vector <edge> e[N];此时我们发现，如果想要找到反向边的话，必须要遍历一遍 e[ed] 数组，这样做的最坏复杂度是
这样的话我们就会在原有的时间复杂度上乘上一个
那么我们如何快速找到反向边呢？
我们不难想到，如果我们记录下反向边的存储位置为 id，那么我们寻找反向边的时候只需要访问 e[ed][id] 就可以了，大大节约了我们的时间。
那么这个 id 的值应该是多少呢？
显然，当我们新加入一条边之前，e[ed] 数组里存的数的个数为 e[ed].size()，它们的下标从 0 到 e[ed].size() - 1，那么新存进来的数的下标一定就是 e[ed].size()，所以 id 直接设为 e[ed].size() 即可。
代码实现：
struct edge {int ed, len, id;};
vector <edge> e[N];加边：
while (m -- )
{
int st, ed, len;
scanf("%lld%lld%lld", &st, &ed, &len);
int sti = e[st].size();
int edi = e[ed].size();
e[st].push_back((edge){ed, len, edi});
e[ed].push_back((edge){st, 0, sti});
}关于 EK 算法的 pre 数组
我们知道在链前实现 EK 算法的时候我们通常会开一个 pre 数组记录当前这个点是走哪条边跳过来的，在 vector 实现时，显然你光记录走哪条边跳过来的用处不大，关键还要知道从哪个点跳过来的。
所以不妨再开一个 lst 数组记录你是从哪个点跳过来的，代码实现如下：
int lst[N], pre[N], d[N];
bool vis[N];
bool bfs()
{
memset(vis, false, sizeof vis);
queue <int> q;
q.push(S);
vis[S] = true;
d[S] = INF;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = 0; i < e[t].size(); i = i + 1)
{
int cur = e[t][i].ed;
if (!vis[cur] && e[t][i].len)
{
vis[cur] = true;
d[cur] = min(d[t], e[t][i].len);
lst[cur] = t;
// lst 记录当前这个点是从第几个点跳过来的
pre[cur] = i;
// pre 记录当前这个点是从第几条边跳过来的
if (cur == T)
return true;
q.push(cur);
}
}
}
return false;
}然后是 EK 算法修改正向边和反向边边权的部分：
int EK()
{
int r = 0;
while (bfs())
{
r += d[T];
for (int i = T; i != S; i = lst[i])
{
e[lst[i]][pre[i]].len -= d[T];
// 从 lst[i] 沿着 pre[i] 跳到 i 的边是正向边
e[i][e[lst[i]][pre[i]].id].len += d[T];
// 从 i 沿着 e[lst[i]][pre[i]].id 跳回 lst[i] 的边是反向边
}
}
return r;
}这个大致就是 EK 算法如何用 vector 实现。
完整代码可以参考：点我查看
vector 实现 Dinic 算法
我们都知道，Dinic 算法和 EK 的最大的不同点在于每次可以增广多条路，而同时增广多条路就需要一个 dfs，这样的话其实我们只要实现了 dfs 的部分，其他就可以用和 EK 一样的方式实现了。
dfs 的部分和链前的部分几乎是一样的，唯一不同的是当前弧优化怎么实现。
这是链式前向星的当前弧优化：
for (int i = cur[st]; ~i; i = nxt[i])
{
cur[st] = i; // 当前弧优化
……
}我们发现，其实就是需要记录当前没有流满的是到哪个点的路径，那么同理到 vector，我们发现也只要记录当前到没有流满的点的第一条路径即可：
for (int i = cur[st]; i < e[st].size(); i = i + 1)
{
cur[st] = i; // 当前弧优化
……
}其实大抵都是一样的，只要解决了找反边的问题，vector 是很容易实现网络流的。
因为 Dinic 算法比较常用，我把 vector 实现 Dinic 算法的完整代码直接贴在下面：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10010, M = 200010, INF = 1e15;
struct edge
{
int ed;
int len;
int id;
};
vector <edge> e[N];
int n, m, S, T;
int dep[N], cur[N];
bool bfs()
{
memset(dep, -1, sizeof dep);
queue <int> q;
q.push(S);
dep[S] = 0;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = 0; i < e[t].size(); i = i + 1)
{
int ed = e[t][i].ed;
if (dep[ed] == -1 && e[t][i].len)
{
dep[ed] = dep[t] + 1;
q.push(ed);
}
}
}
memset(cur, 0, sizeof(cur));
return (dep[T] != -1);
}
int dfs(int st, int limit)
{
if (st == T)
return limit;
for (int i = cur[st]; i < e[st].size(); i = i + 1)
{
cur[st] = i; // 当前弧优化
int ed = e[st][i].ed;
if (dep[ed] == dep[st] + 1 && e[st][i].len)
{
int t = dfs(ed, min(e[st][i].len, limit));
if (t)
{
e[st][i].len -= t;
e[ed][e[st][i].id].len += t;
return t;
}
else
dep[ed] = -1;
}
}
return 0;
}
int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = dfs(S, INF)) r += flow;
return r;
}
signed main()
{
cin >> n >> m >> S >> T;
while (m -- )
{
int st, ed, len;
cin >> st >> ed >> len;
int sti = e[st].size();
int edi = e[ed].size();
e[st].push_back((edge){ed, len, edi});
e[ed].push_back((edge){st, 0, sti});
}
cout << dinic();
return 0;
}完美，撒花
✿✿ヽ(°▽°)ノ✿