费用流

OI 知识>图论
1.3k words

费用流

一，相关概念

给定一网络 \(G=(V,E)\)，除了有容量限制 \(c(u,v)\) 外，还给出了单位流量费用 \(w(u,v)\)，要求在最大化 \(\sum_{(s,v)\in E}f(s,v)\) 即网络总流量的情况下最小化 \(\sum_{(u,v)\in E}f(u,v)\times\) \(w(u,v)\)。这种问题被称为最小费用最大流。

费用满足斜对称性，即 \(w(u,v)=-w(v,u)\)，这一性质的实际意义使在有流量的情况向反向流相当于退费。

二，求法

1. SSP 算法

SSP 算法是一个贪心算法，其核心思路是每次寻找单位费用最小的增广路进行增广直到图中不存在增广路为止。

如果图中存在单位费用为负的负圈，SSP 算法无法正确求出网络的最小费用最大流，此时需要先使用消圈算法消去图上负圈。

正确性证明

设流量为 \(i\) 的时候最小费用为 \(f_i\)。假设最初网络上无负圈，这时 \(f_0=0\)。

假设 SSP 算法求出的 \(f_i\) 是最小费用，在 \(f_i\) 的基础上找到一条最短增广路，求出 \(f_{i+1}\)，此时 \(f_{i+1}-f_i\) 是这一增广路的长度。

假设存在更小的费用 \(f_{i+1}'\)，由于 \(f_{i+1}-f_i\) 已经是最短增广路了，所以 \(f_{i+1}'-f_i\) 一定对应一个经过至少一个负环的增广路。此时 \(f_i\) 就不是最小费用了（可以给负圈添加流量使得 \(f_i\) 流量更小），与条件矛盾，则不存在更小费用 \(f_{i+1}'\)。

综上，SSP 算法可以求出无负圈网络的最小费用最大流。

实现

只需要将 EK 算法或 Dinic 算法中找增广路的过程替换为用最短路算法寻找单位费用最小的增广路即可。

基于 EK 算法的实现（抬走，下一位）： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct edge {int to,nxt,f,c} e[2*M];
int h[N],cnt=1;
void addin(int x,int y,int f,int c)
{
    e[++cnt]={y,head[x],f,c},head[x]=cnt;
    e[++cnt]={x,head[y],0,-c},head[y]=cnt;
}
int dis[N],pre[N],incf[N];
bool vis[N];
bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s),dis[s]=0,incf[s]=inf;
    while(!q.empty())
    {
        int u=q.front(); q.pop(),vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=edge[i].to;
            if(dis[v]<=dis[u]+e[i].c||!e[i].f) continue;
            dis[v]=dis[u]+c,incf[v]=min(e[i].f,incf[u]),pre[v]=i;
            if(!vis[v]) q.push(v),vis[v]=1;
        }
    }
    return incf[t];
}
int mxf,mnc;
void update()
{
    mxf+=incf[t];
    for(int u=t;u!=s;u=e[pre[u]^1].to)
    {
        e[pre[u]].f-=incf[t],e[pre[u]^1].f+=incf[t];
        mnc+=incf[t]*e[pre[u]].c;
    }
}
...
while(spfa()) update()

基于 Dinic 算法的实现： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
int const N=5005,M=100005,inf=0x3f3f3f3f;
int n,m,s,t,u,v,w,c,mxf,mnc,cnt,head[N],dis[N],vis[N],cur[N];
struct edge{int to,nxt,f,c;} e[M];
void addin(int x,int y,int f,int c)
{
    e[++cnt]={y,head[x],f,c},head[x]=cnt;
    e[++cnt]={x,head[y],0,-c},head[y]=cnt;
}
bool spfa()
{
    memset(dis,inf,sizeof(dis));
    memcpy(cur,head,sizeof(cur));
    queue<int> q;
    q.push(s),dis[s]=0,vis[s]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop(),vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(dis[v]<=dis[u]+e[i].c||!e[i].f) continue;
            dis[v]=dis[u]+e[i].c;
            if(!vis[v]) q.push(v),vis[v]=1;
        }
    }
    return dis[t]!=inf;
}
int dfs(int u,int F)
{
    if(u==t) return F;
    vis[u]=1;
    int lst=0;
    for(int i=cur[u];i&&lst<F;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(vis[v]||dis[v]!=dis[u]+e[i].c||!e[i].f) continue;
        int k=dfs(v,min(F-lst,e[i].f));
        if(k) e[i].f-=k,e[i^1].f+=k,mnc+=k*e[i].c,lst+=k;
    }
    vis[u]=0;
    return lst;
}
int mcmf()
{
    int ret=0;
    while(spfa())
    {
        int k=dfs(s,inf);
        while(k) ret+=k,k=dfs(s,inf);;
    }
    return ret;
}
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(int x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
int main()
{
    n=rd(),m=rd(),s=rd(),t=rd(),cnt=1;
    for(int i=1;i<=m;i++)
        u=rd(),v=rd(),w=rd(),c=rd(),addin(u,v,w,c);
    mxf=mcmf();
    wt(mxf),putchar(' '),wt(mnc);
    return 0;
}

2. Primal-Dual 原始对偶算法

在此仅做简单讲解，不做正确性证明。

过程

用 SPFA 求最短路的时间复杂度是 \(O(nm)\) 的，不及 Dijkstra 算法，但由于网络中存在费用为负的边，无法直接使用 Dijkstra。

Primal-Dual 原始对偶算法的思路与Johnson 全源最短路类似，为每个点设置一个势能，使所有边的费用均变为非负，从而可以用 Dijkstra 找出网络上单位费用最小的增广路。

首先跑一次最短路，找出源点到每个点的最短距离 \(h_i\)，之后和 Johnson 算法一样，对于一条从 \(u\) 到 \(v\) 的单位为 \(w\) 的边，将其费用重置为 \(w+h_u-h_v\)。

与常规最短路问题不同的是，每次增广后图的形态会发生变化，这种情况下各点是能需要更新。设增广后从源点到 \(i\) 号点的距离为 \(d_i'\)（这里的距离是重置各边费用后的距离），只需要给 \(h_i\) 加上 \(d_i'\) 即可。

实现

由于不会 Johnson 最短路，只能放上 OI-wiki 了，之后会更新正确性证明和实现代码 OI-wiki。

Comments