网络流初步（3）—— 费用流

填坑。

前两期：
网络流初步 —— 最大流算法 (2023/01/25)
网络流初步（2）—— 最小割 (2023/01/26)

费用流

现在，网络中新增了一个属性：费用。

设边 $u,v$ 的费用为 $w(u,v)$。则当 $(u,v)$ 的流量为 $f(u,v)$ 时，费用为 $f(u,v)w(u,v)$。
现在，你需要保证流量最大的前提下，使费用最小，称作最小费用最大流（Min Cost Max Flow）。

做法

算法

用贪心算法。只需每次找费用最小的增广路，然后不断增广即可，证明略去，但是记住只要没有负圈这个算法就是正确的。（注意：原图费用不可以出现负圈）

数据结构

怎么存图？注意在费用流中是需要处理重边问题的，还需要方便的获取反向边。

习惯上，我们采用的是边表+邻接表记录出边在边表中的下标的数据结构。一条边和他反向边是存在一起的，即在边表的下标可以通过异或 1 得到。（0^1=1，1^1=0，6^1=7,7^1=6）

如果不明白，看以下代码理解。

struct Edge{
    int u,v; // 起点,终点
    ll w,c,f; // 费用,容量,流量
};

// 对于一条下标为 i 的边，edges[i^1] 就是它的反向边 
vector<Edge> edges; // 存放所有的边
vector<int> G[N]; // G[u] 存放 u 的所有出边在 edges 里的下标

void add_edge(int u,int v,int w,int c){
    edges.push_back({u,v,w,c,0}); // 正向边插入边表
    edges.push_back({v,u,-w,0,0}); // 反向边插入边表
    auto cnt = edges.size();
    G[u].push_back(cnt-2); // 这条从u出发的正向边在edges里的下标是cnt-2
    G[v].push_back(cnt-1); // 这条从v出发的反向边在edges里的下标是cnt-1
}

找费用最小的增广路

用 SPFA，即队列优化的 Bellman-Ford 算法。找到后和 EK 算法思路一样进行增流。

const ll INF = 0x3f3f3f3f3f3f3f3f;
int s,t;
ll d[N]; // 距离
bool inq[N]; // 在spfa队列中吗？
int fa[N]; // 节点 u 是从哪条**边**跳过来的？存的是边的下标，不是点！
ll a[N]; // 可改进量。只有 a[t] 是真正需要的，也是这次真正的改进量

ll flow=0,cost=0; // 答案

bool SPFA(){
    memset(d,0x3f,sizeof(d));
    d[s]=0;a[s]=INF;
    queue<int> q;
    q.push(s);inq[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();inq[u]=0;
        for(int ind:G[u]){
            auto& edge = edges[ind];
            if(edge.c > edge.f && d[edge.v] > d[u] + edge.w){
                d[edge.v]=d[u]+edge.w;
                a[edge.v]=min(a[u],edge.c-edge.f);
                fa[edge.v] = ind;
            
                if(!inq[edge.v]){
                    q.push(edge.v);inq[edge.v]=1;
                }
            }
        }
    }

    if(d[t]==INF)return 0; // 已经没有增广路了

    // 开始增流
    flow += a[t];
    cost += a[t]*d[t]; // 增加费用
    int now = t;
    while(now!=s){
        int ind = fa[now];
        edges[ind].f += a[t]; // 正向边增加流量
        edges[ind^1].f -= a[t]; // 反向边减少流量
        now = edges[ind].u;
    }
    return 1;
}

主过程

只需要一行即可。

while(SPFA());

完整代码

洛谷P3381 【模板】最小费用最大流

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

const int N = 5e3+5;

struct Edge{
    int u,v; // 起点,终点
    ll w,c,f; // 费用,容量,流量
};

// 对于一条下标为 i 的边，edges[i^1] 就是它的反向边 
vector<Edge> edges; // 存放所有的边
vector<int> G[N]; // G[u] 存放 u 的所有出边在 edges 里的下标

void add_edge(int u,int v,int w,int c){
    edges.push_back({u,v,w,c,0}); // 正向边插入边表
    edges.push_back({v,u,-w,0,0}); // 反向边插入边表
    auto cnt = edges.size();
    G[u].push_back(cnt-2); // 这条从u出发的正向边在edges里的下标是cnt-2
    G[v].push_back(cnt-1); // 这条从v出发的反向边在edges里的下标是cnt-1
}

const ll INF = 0x3f3f3f3f3f3f3f3f;
int s,t;
ll d[N]; // 距离
bool inq[N]; // 在spfa队列中吗？
int fa[N]; // 节点 u 是从哪条**边**跳过来的？存的是边的下标，不是点！
ll a[N]; // 可改进量。只有 a[t] 是真正需要的，也是这次真正的改进量

ll flow=0,cost=0; // 答案

bool SPFA(){
    memset(d,0x3f,sizeof(d));
    d[s]=0;a[s]=INF;
    queue<int> q;
    q.push(s);inq[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();inq[u]=0;
        for(int ind:G[u]){
            auto& edge = edges[ind];
            if(edge.c > edge.f && d[edge.v] > d[u] + edge.w){
                d[edge.v]=d[u]+edge.w;
                a[edge.v]=min(a[u],edge.c-edge.f);
                fa[edge.v] = ind;
            
                if(!inq[edge.v]){
                    q.push(edge.v);inq[edge.v]=1;
                }
            }
        }
    }

    if(d[t]==INF)return 0;

    // 开始增流
    flow += a[t];
    cost += a[t]*d[t]; // 增加费用
    int now = t;
    while(now!=s){
        int ind = fa[now];
        edges[ind].f += a[t]; // 正向边增加流量
        edges[ind^1].f -= a[t]; // 反向边减少流量
        now = edges[ind].u;
    }
    return 1;
}


int main(){
    int n,m;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=0;i<m;i++){
        int u,v,w,c;
        scanf("%d%d%d%d",&u,&v,&w,&c);
        add_edge(u,v,c,w);
    }

    while(SPFA());

    printf("%lld %lld\n",flow,cost);
    return 0;
}