# 网络流: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 的等价图为 GG',其对应的边 (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++wuk1,ukw_{u_1,u_2}+w_{u_2,u_3}+\dots+w_{u_{k-1},u_k}

GG' 中的权值可化简为

wu1,u2+wu2,u3++wuk1,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)

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

dud_{u} 为图 GG 中源点 ss 到点 uu 的最短路径,图 GG' 中为 dud'_{u},显然有

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

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

# 势函数

# 初值

如果网络 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;
}
更新于