最小费用流(沿Dijkstra最短路增广)

最小费用流

最小费用流问题：

在最大流问题的网络中，给边新加上费用，求流量为f时费用的最小值

最大流：残余网络上贪心增广

最小费用流：残余网络上沿着最短路增广

Attention

残余网络中反向边的权值是原边权值的相反数，意味着会有负权边，所以一般用Bellman_Ford求最短路。但它时间复杂度较高，可以考虑导入“势”的概念用Dijkstra求最短路

Dijkstra最短路上增广（模板）

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;///first:最短距离 second:节点编号
typedef long long ll;

struct edge{ int to, w, cap, rev; };

int n, m, s, t, flow;
vector<edge> vec[N];
int h[N], dis[N];///节点的势 最短距离
int fro_v[N], fro_e[N];///vector 的 第一维和第二维
///用于确定最短路中点k前面那条边

void add(int from, int to, int w, int cap)
{
    int from_sz = vec[from].size(), to_sz = vec[to].size();
    vec[from].push_back( (edge){ to, w, cap, to_sz } );
    vec[to].push_back( (edge){ from, -w, 0, from_sz } );
}

int min_cost_flow(int s, int t, int f)
{
    ll res = 0;
    memset(h, 0, sizeof(h));
    while(f)///若没完成任务：就对残余网络搜索最短路进行增广
    {
        priority_queue<P, vector<P>, greater<P> > q;
        memset(dis, INF, sizeof(dis));
        dis[s] = 0;
        q.push(P(0, s));
        while(!q.empty())
        {
            P now = q.top();
            q.pop();
            int to = now.second;
            if(dis[to] < now.first)
                continue;
            for(int i = 0; i < vec[to].size(); ++i)
            {
                edge & nxt = vec[to][i];
                if(nxt.cap > 0 && dis[nxt.to] > dis[to] + nxt.w + h[to] - h[nxt.to])
                {
                    dis[nxt.to] = dis[to] + nxt.w + h[to] - h[nxt.to];
                    fro_v[nxt.to] = to;
                    fro_e[nxt.to] = i;
                    q.push(P(dis[nxt.to], nxt.to));
                }
            }
        }
        if(dis[t] == INF)///还未完成任务（f减为0）就找不出可行流了
            return -1;
        for(int v = 0; v <= n; ++v)
            h[v] += dis[v];

        int d = f;///保证f最终为0而非小于0
        ///即使新的最大流>f, 也只取f
        for(int v = t; v != s; v = fro_v[v])
            d = min(d, vec[ fro_v[v] ][ fro_e[v] ].cap);

        f -= d;
        res += d * h[t];///There is a h[t] in Dijkstra, not a dis[t](in Bellman_Ford).
        for(int v = t; v != s; v = fro_v[v])///更新残余网络，建反向边
        {
            edge & nxt = vec[ fro_v[v] ][ fro_e[v] ];
            nxt.cap -= d;
            vec[v][nxt.rev].cap += d;
        }
    }
    return res;
}

int main()
{
    freopen("00in.txt", "r", stdin);
    scanf("%d%d%d%d%d", &n, &m, &s, &t, &flow);
    int ui, vi, wi, fi;
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d%d", &ui, &vi, &wi, &fi);
        add(ui, vi, fi, wi);
    }
    cout << min_cost_flow(s, t, flow) << '\n';
    return 0;
}
Copy
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

详见《挑战程序设计竞赛（第2版）》Page225

本想找个模板题试试，结果模板题都是最小费用最大流