← 返回教学内容

【洛谷】P3381 最小费用最大流

算法 · 题解 · 图论

写一篇题解来加深印象。其他题解都没有说明复杂度的问题和常见易错点。本文将介绍用 vector 来存图，采用 spfa + dinic 的算法，也就是 SSP 算法。

SSP 算法

默认读者已经学会了最大流算法。现在，我们每条边加上单位流量的费用，要求在最大流的基础上满足费用最小，这就是最小费用最大流问题。

简单来说，我们每次贪心地选择费用最小的增广路增广，直到不存在增广路时终止算法。需要注意的是，图中不能有负圈，如果存在负圈，首先要用消圈算法消除负圈。存在负圈的题目这是一道有负圈的费用流模板题。

现在证明一下贪心的正确性。我们已知图中不存在负圈。假设流量为 $i$ 的流的费用为 $f_i$，我们通过增广一次最短增广路求出 $f_j$。如果存在另一种从 $f_i$ 增广一次增广路且小于 $f_j$ 的费用流 $f_k$，则该增广必然走过负圈，与已知图中不存在负圈矛盾，所以贪心是可行的。

由于极端情况下 spfa 找增广路的时间复杂度为 $O(nm)$，故 SSP 算法的复杂度为 $O(nmf)$，其中 $f$ 为网络最大流，需要注意的是，这并不是一个多项式复杂度，例如 $f = 2^{n/2}$ 时，复杂度为指数级别。

实现代码时，可能存在一些易错点。首先，用 vector 来存图，找反向边时需要添加对应编号快速寻找反向边，其次，反向边的费用应该是 $-c$，这样走反向边时才满足最短路的判断条件，正向边的条件为 $dis[v]=dis[u]+c$，反向边就是 $dis[u]=dis[v]+(-c)$。最后，跑一次 spfa 应该多次 dfs 找增广路而不是只找一次，有的题目会卡只找一次的代码。

附上代码。

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define int long long//开longlong
using namespace std;
const int N = 5e3 + 5;
const int inf = 0x7fffffff;
int n, m, s, t, mincos;
struct node
{
    int v, w, c, id;
};
vector<node> val[N];
int dis[N], cur[N];
bool vis[N];

bool spfa()
{
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for (auto &e : val[x])
            if (e.w && dis[e.v] > dis[x] + e.c)
            {
                dis[e.v] = dis[x] + e.c;
                if (!vis[e.v])
                    q.push(e.v), vis[e.v] = true;
            }
    }
    return dis[t] != inf;//如果存在增广路就返回true，否则返回false
}

int dfs(int x, int res)
{
    if (x == t || !res)
        return res;
    vis[x] = true;
    int used = 0;
    for (int i = cur[x]; i < val[x].size(); ++i)
    {
        auto &e = val[x][i];
        cur[x] = i;//当前弧优化
        if (!vis[e.v] && e.w && dis[e.v] == dis[x] + e.c)
        {
            int cnt = dfs(e.v, min(res - used, e.w));//递归找流量
            if (cnt)
            {
                e.w -= cnt;
                val[e.v][e.id].w += cnt;
                mincos += cnt * e.c;
                used += cnt;
                if (used == res)
                    break;//残留优化
            }
        }
    }
    vis[x] = false;
    return used;
}

int dinic()
{
    int ans = 0, flow;
    while (spfa())
    {
        memset(cur, 0, sizeof(cur));
        while ((flow = dfs(s, inf)))//一次spfa要找多次增广路
            ans += flow;
    }
    return ans;
}

signed main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    for (int i = 1; i <= m; ++i)
    {
        int u, v, w, c;
        scanf("%lld%lld%lld%lld", &u, &v, &w, &c);
        val[u].push_back({v, w, c, (int)val[v].size()});//记录反向边的id
        val[v].push_back({u, 0, -c, (int)val[u].size() - 1});//记录反向边的id
    }
    int maxflow = dinic();
    printf("%lld %lld\n", maxflow, mincos);
    return 0;
}
评论