这篇博客这是记录网络流板子的，不进行网络流的讲解。用注释标注了一些易错或重要步骤。
Dinic（无当前弧优化）
dinic 的当前弧优化其实快不了多少，而且容易出事。
完整代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxM = 1e5 + 3;
const int maxN = 1e4 + 3;
const int INF = 0x3f3f3f3f;
struct Edge {
int next, to, cap;
} edge[maxM << 1];
int head[maxN], lvl[maxN];
int n, m, cnt = -1, s, t; // cnt 需要初始化为奇数，因为需要用异或(^)表示反向边
void add(int from, int to, int cost) {
edge[++cnt] = (Edge) {head[from], to, cost};
head[from] = cnt;
}
void addEdge(int from, int to, int cost) {
add(from, to, cost);
add(to, from, 0);
}
queue<int> que;
bool bfs() { // BFS 标号过程
memset(lvl, -1, sizeof(lvl));
lvl[s] = 0;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (lvl[v] < 0 && edge[i].cap) {
lvl[v] = lvl[u] + 1;
que.push(v);
}
}
}
return lvl[t] != -1;
}
int dfs(int u, int f) {
if (!f || u == t) return f;
int flow = 0;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (lvl[v] == lvl[u] + 1 && edge[i].cap) {
int d = dfs(v, min(f, edge[i].cap));
flow += d;
f -= d;
edge[i].cap -= d;
edge[i ^ 1].cap += d;
}
}
if (!flow) lvl[u] = -1;
return flow;
}
int dinic() {
int ans = 0;
while (bfs()) ans += dfs(s, INF);
return ans;
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addEdge(a, b, c);
}
printf("%d\n", dinic());
return 0;
}最小费用最大流（SPFA 版）
就是把 dinic 算法中 BFS 标号过程魔改成了 SPFA，求最大流是根据进行 SPFA 所记录的路径进行的。
完整代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxM = 5e4 + 3, maxN = 5e3 + 3;
const int INF = 0x7f7f7f7f;
struct Edge {
int next, to, cap, cost;
} edge[maxM << 1];
int head[maxN], dis[maxN], pre[maxN], preEdge[maxN];
bool vis[maxN];
int s, t, n, m, cnt = -1, minCost, maxFlow;
void add(int from, int to, int val, int cost) {
edge[++cnt] = (Edge) {head[from], to, val, cost};
head[from] = cnt;
}
void addEdge(int from, int to, int val, int cost) {
add(from, to, val, cost);
add(to, from, 0, -cost);
}
queue<int> que;
bool spfa() {
memset(dis, 0x7f, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[s] = 0;
vis[s] = true;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] > dis[u] + edge[i].cost && edge[i].cap) {
dis[v] = dis[u] + edge[i].cost;
pre[v] = u; // 用于记录路径，记录当前点所连的前一个点
preEdge[v] = i; // 记录路径，记录当前点所连的前一条边
if (!vis[v]) {
que.push(v);
vis[v] = true;
}
}
}
}
return dis[t] != INF;
}
void work() {
while (spfa()) {
int flow = INF;
for (int i = t; i != s; i = pre[i])
flow = min(flow, edge[preEdge[i]].cap);
maxFlow += flow;
minCost += dis[t] * flow;
for (int i = t; i != s; i = pre[i]) {
edge[preEdge[i]].cap -= flow;
edge[preEdge[i] ^ 1].cap += flow;
}
}
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int a, b, x, y;
scanf("%d%d%d%d", &a, &b, &x, &y);
addEdge(a, b, x, y);
}
work();
printf("%d\n", minCost);
return 0;
}