网络流：Dijkstra 求费用流

注：下文中的边权 $w$ 均表示费用 $f$。

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

最短路

在任意残留网络中的任意边 $(u,v)$ 都需要满足：
$$
w_{u, v}+h(u) - h(v)≥0
$$
令图 $G$ 的等价图为 $G’$，其对应的边 $(u,v)$ 的权值为
$$
w’{u,v} = w{u,v} + h(u) - h(v)
$$
因此，对于原图中的任意一条路径 $(u_1,u_2,\dots,u_k)$，它在 $G$ 中的权值为
$$
w_{u_1,u_2}+w_{u_2,u_3}+\dots+w_{u_{k-1},u_k}
$$
在 $G’$ 中的权值可化简为
$$
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$ 上。

令 $d_{u}$ 为图 $G$ 中源点 $s$ 到点 $u$ 的最短路径，图 $G’$ 中为 $d’_{u}$，显然有

$$
d_{u,v} = d’_{u,v}-h(u)+h(v)
$$
所以我们只需要求 $G’$ 的最短路径，就能对应回原图的最短路径。

势函数

初值

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

证明略。

维护

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

证明：对于残余网络上的任意边 $(u,v)$，均有
$$
dis[u]+w_{u,v}+h(u)-h(v)≥dis[v]
$$
移项，得
$$
w_{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;
}