首页 算法 网络流

# 网络流：Dijkstra 求费用流

注：下文中的边权 ww 均表示费用 ff。

Dijkstra 不能求有负权边的最短路，所以我们可以对网络 GG 中的每一个点设置一个势函数 h(u)h(u)，以满足在与原图等价的新图中的边权非负。

# 最短路

在任意残留网络中的任意边 (u,v)(u,v) 都需要满足：

wu,v+h(u)−h(v)≥0w_{u, v}+h(u) - h(v)≥0

令图 GG 的等价图为 G′G'，其对应的边 (u,v)(u,v) 的权值为

wu,v′=wu,v+h(u)−h(v)w'_{u,v} = w_{u,v} + h(u) - h(v)

因此，对于原图中的任意一条路径 (u1,u2,…,uk)(u_1,u_2,\dots,u_k)，它在 GG 中的权值为

wu1,u2+wu2,u3+⋯+wuk−1,ukw_{u_1,u_2}+w_{u_2,u_3}+\dots+w_{u_{k-1},u_k}

在 G′G' 中的权值可化简为

wu1,u2+wu2,u3+⋯+wuk−1,uk+h(u1)−h(uk)w_{u_1,u_2} + w_{u_2,u_3} + \dots + w_{u_{k-1}, u_k} + h(u_1)-h(u_k)

所以，在 G′G' 求出的路径都可以对应到 GG 上。

令 dud_{u} 为图 GG 中源点 ss 到点 uu 的最短路径，图 G′G' 中为 du′d'_{u}，显然有

du,v=du,v′−h(u)+h(v)d_{u,v} = d'_{u,v}-h(u)+h(v)

所以我们只需要求 G′G' 的最短路径，就能对应回原图的最短路径。

# 势函数

# 初值

如果网络 GG 初始边权非负，则令 h(u)=0h(u)=0 ，否则可令 h(u)=dis[u]h(u) = dis[u]（用 SPFA 解决）。

证明略。

# 维护

每次增广后，令 h(u)=h(u)+dis[u]h(u)=h(u)+dis[u] 即可。

证明：对于残余网络上的任意边 (u,v)(u,v)，均有

dis[u]+wu,v+h(u)−h(v)≥dis[v]dis[u]+w_{u,v}+h(u)-h(v)≥dis[v]

移项，得

wu,v+(h(u)+dis[u])−(h(v)+dis[v])≥0w_{u,v}+(h(u)+dis[u])-(h(v)+dis[v]) \geq 0

证毕。

# P3381 ［模板］最小费用最大流

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline
const int N = 5500, M = 55000, INF = 0x3f3f3f3f;
struct point {
    int u, val;
    point(int _u = 0, int _val = 0): u(_u), val(_val) {}
    bool operator < (const point &o) const { return val > o.val; } 
};
priority_queue <point> q;
struct node {
    int u, v, w, f, next;
    node() {}
} e[M << 1];
int head[N], tot = 0;
il void add(int u, int v, int w, int f) {
    e[tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].f = f;
    e[tot].next = head[u]; head[u] = tot++;
}
int h[N], dis[N], flow[N], pre[N];
int n, m, s, t;
int maxflow = 0, mincost = 0;
il bool dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    memset(pre, -1, sizeof pre);
    
    dis[s] = 0;
    q.push(point(s, 0));
    while (!q.empty()) {
        int u = q.top().u, val = q.top().val;
        q.pop();
        if (val > dis[u]) continue;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w and dis[v] > dis[u] + e[i].f + h[u] - h[v]) {
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                dis[v] = dis[u] + e[i].f + h[u] - h[v];
                q.push(point(v, dis[v]));
            }
        }
    }
    return dis[t] != INF;
}
il void check() {
    
    for (int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    maxflow += flow[t];
    mincost += (dis[t] - h[s] + h[t]) * flow[t];
    
    for(int i=1; i<=n; ++i) h[i] += dis[i];
}
int main() {
    
    freopen("p3381.in", "r", stdin);
    
    memset(head, -1, sizeof head);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while (dijkstra()) check();
    printf("%d %d\n", maxflow, mincost);
    
    return 0;
}