网络最大流和费用流板子

这篇博客这是记录网络流板子的，不进行网络流的讲解。用注释标注了一些易错或重要步骤。

Dinic（无当前弧优化）

dinic 的当前弧优化其实快不了多少，而且容易出事。

完整代码

#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 所记录的路径进行的。

完整代码

#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;
}