主页
归档
朋友
关于

算法学习笔记-最小费用最大流

前言

某天我看到了memset0巨佬怒切17道网络流神仙题的时候，我顿时准备去做做看网络流24题以满足我内心的抖M之魂

于是，我这个蒟蒻看到某道费用流神题的时候，一脸懵逼地看着“费用流”的标签，决心去学一学这玩意

定义

最小费用最大流（费用流）是在最大流的基础上，要求我们取到的总共需要的费用最小化。

同时每个边所消耗的费用都是与它这条边的流量成正比的

实现

我们看一看增广路做最大流的做法（以Dinic为例）

首先，我们通过BFS确定是否拥有一条从源点流向汇点的增广路径，如果存在，说明当前搜到的不是最优解，继续进行，如果没有，退出程序

然后，如果我们要保证这条路径需要的费用最小化（将BFS改为SPFA，将DFS改为记录路径），便可以保证在我们搜到最优解的时候保证我们在保证流量最大的同时保证费用最小

证明

tan90Otan90^{O}

这种一个“感性理解”解决的东西需要严格证明吗？

代码

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
// Sooke bless me.
// LJC00118 bless me.
#include<bits/stdc++.h>

using namespace std;

#define INF 2147483647
#define ll long long

int Inp(){
    char c = getchar();
    int Neg = 1;
    while(c < '0' || c > '9'){
        if(c == '-')
            Neg = -1;
        c = getchar();
    }
    int Sum = 0;
    while(c >= '0' && c <= '9'){
        Sum = ((Sum << 3) + (Sum << 1)) + c - '0';
        c = getchar();
    }
    return Neg * Sum;
}

int Head[5010];
int Next[200010];
int End[200010];
int Value[200010];
int Cost[200010];
int Dis[5010];
int Prev1[5010];
int Prev2[5010];
bool Inq[10000];
int q[1000010];
int Cou = -1;

void Link(int a, int b, int v, int c){
    Next[++Cou] = Head[a];
    Head[a] = Cou;
    End[Cou] = b;
    Value[Cou] = v;
    Cost[Cou] = c;
}

int main(){
    memset(Head, -1, sizeof(Head));
    int n = Inp();
    int m = Inp();
    int s = Inp();
    int e = Inp();
    for(int i = 1; i <= m; i++){
        int a = Inp();
        int b = Inp();
        int v1 = Inp();
        int v2 = Inp();
        Link(a, b, v1, v2);
        Link(b, a, 0, -v2);
    }
    int Flow = 0;
    int Ans = 0;
    int f = INF;
    while(f > 0){
        memset(Inq, false, sizeof(Inq));
        for(int i = 1; i <= n; i++)
            Dis[i] = INF;
        Dis[s] = 0;
        q[5000] = s;
        int qf = 5000;
        int qe = 5000;
        int Sum = 0;
        while(qf <= qe){ // SPFA（因为会有负权所以用SPFA）
            int u = q[qf++];
            Inq[u] = false;
            Sum -= Dis[u];
            for(int x = Head[u]; x != -1; x = Next[x]){
                if(Value[x] > 0 && Dis[End[x]] > Dis[u] + Cost[x]){
                    if(Inq[End[x]])
                        Sum -= Dis[End[x]];
                    Dis[End[x]] = Dis[u] + Cost[x];
                    Prev1[End[x]] = u;
                    Prev2[End[x]] = x;
                    Sum += Dis[End[x]];
                    if(!Inq[End[x]]){
                    	q[++qe] = End[x];
                        Inq[End[x]] = true;
                    }
                }
            }			
        }

        if(Dis[e] == INF)
            break;
        int Delta = f;
        for(int i = e; i != s; i = Prev1[i])
            Delta = min(Delta, Value[Prev2[i]]);
        f -= Delta;
        Flow += Delta;
        Ans += Delta * Dis[e];
        for(int i = e; i != s; i = Prev1[i]){
            Value[Prev2[i]] -= Delta;
            Value[Prev2[i] ^ 1] += Delta;
        }
    }
    printf("%d %d", Flow, Ans);
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动，使用 Azurus 作为主题。