最小费用最大流，指在保证最大流量的同时最小费用。

网络流系列文章

  1. 最大流
  2. 最小割
  3. 费用流
  4. 上下界网络流

概念

费用

我们定义一条边的费用 $w(u,v)$ 表示边 $(u,v)$ 上单位流量的费用。也就是说，当边 $(u,v)$ 的流量为 $f(u,v)$ 时，需要花费 $f(u,v)\times w(u,v)$ 的费用。

最小费用最大流

网络流图中，花费最小的最大流被称为最小费用最大流，这也是接下来我们要研究的对象。

求解

我们可以在 $\text{Dinic}​$ 算法的基础上进行改进，把 $\text{BFS}​$ 求分层图改为用 $\text{SPFA}​$（由于有负权边，所以不能直接用 $\text{Dijkstra}​$）来求一条单位费用之和最小的路径，也就是把 $w(u,v)​$ 当做边权然后在残量网络上求最短路，当然在 $\text{DFS}​$ 中也要略作修改。这样就可以求得网络流图的最小费用最大流了。

如何建反向边？对于一条边 $(u,v,w,c)$（其中 $w$ 和 $c$ 分别为容量和费用），我们建立正向边 $(u,v,w,c)$ 和反向边 $(v,u,0,-c)$（其中 $-c$ 是使得从反向边经过时退回原来的费用）。

优化：如果你是“关于 $\text{SPFA}$，它死了”言论的追随者，那么你可以使用 $\text{Primal-Dual}$ 原始对偶算法将 $\text{SPFA}$ 改成 $\text{Dijkstra}$！

时间复杂度：可以证明上界为 $\mathcal O(nmf)$，其中 $f$ 表示流量。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 2e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, s, t, dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M];
bool vis[N];

void add(int u, int v, int w, int c) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addEdge(int u, int v, int w, int c) {
    add(u, v, w, c), add(v, u, 0, -c);
}
bool spfa(int s, int t) {
    memset(dis, 0x7f, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0, vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = false;
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] > dis[u] + cost[i]) {
                dis[v] = dis[u] + cost[i];
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
    return dis[t] < INF;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    vis[u] = true;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) break;
        }
    }
    vis[u] = false;
    return ans;
}
std::pair<int, int> dinic(int s, int t) {
    int maxFlow = 0, minCost = 0;
    while (spfa(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) maxFlow += x, minCost += x * dis[t];
    }
    return std::make_pair(maxFlow, minCost);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w, c;
        scanf("%d%d%d%d", &u, &v, &w, &c);
        addEdge(u, v, w, c);
    }
    std::pair<int, int> ans = dinic(s, t);
    printf("%d %d\n", ans.first, ans.second);
    return 0;
}

习题

网络流 24 题

最后修改：2019 年 06 月 28 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏