20220104-费用流
费用流
1. 最小费用最大流Minimum Cost Maximum Flow
- 基本概念：网络上的每条边，除了容量外，还有一个属性：单位费用。一条边上的
费用 = 流量 × 单位费用； - 解决思路：我们已经知道，只要建了反向边，无论增广的顺序是怎样的，都能求出最大流。所以我们只需要每次都增广费用最少的一条路径即可。具体而言，将EK算法中的BFS换成SPFA即可；
2. 典型举例
模板题
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
using namespace std;
const int N = 5010, M = 100010, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d){
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
bool spfa(){
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while(hh != tt){
int t = q[hh++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int ver = e[i];
if(f[i] && d[ver] > d[t] + w[i]){
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if(!st[ver]){
q[tt++] = ver;
if(tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
void EK(int& flow, int& cost){
flow = cost = 0;
while(spfa()){
int t = incf[T];
flow += t, cost += t * d[T];
for(int i = T; i != S; i = e[pre[i] ^ 1]){
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}
int main(){
cin>>n>>m>>S>>T;
memset(h, -1, sizeof h);
while(m--){
int a, b, c, d; cin>>a>>b>>c>>d;
add(a, b, c, d);
}
int flow, cost;
EK(flow, cost);
cout<<flow<<" "<<cost<<endl;
return 0;
}
运输问题
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
using namespace std;
const int N = 160, M = 5150 * 2 + 10, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d){
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
bool spfa(){
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while(hh != tt){
int t = q[hh++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int ver = e[i];
if(f[i] && d[ver] > d[t] + w[i]){
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(incf[t], f[i]);
if(!st[ver]){
q[tt++] = ver;
if(tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
int EK(){
int cost = 0;
while(spfa()){
int t = incf[T];
cost += t * d[T];
for(int i = T; i != S; i = e[pre[i] ^ 1]){
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
return cost;
}
int main(){
cin>>m>>n;
S = 0, T = m + n + 1;
memset(h, -1, sizeof h);
for(int i = 1; i <= m; i++){
int a; cin>>a;
add(S, i, a, 0);
}
for(int i = 1; i <= n; i++){
int b; cin>>b;
add(m + i, T, b, 0);
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
int c; cin>>c;
add(i, m + j, INF, c);
}
}
cout<<EK()<<endl;
for(int i = 0; i < idx; i += 2){
f[i] += f[i ^ 1], f[i ^ 1] = 0;
w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
}
cout<<-EK()<<endl;
return 0;
}负载平衡问题
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
using namespace std;
const int N = 110, M = 610, INF = 1e8;
int n, S, T;
int s[N];
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d){
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}
bool spfa(){
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while(hh != tt){
int t = q[hh++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int ver = e[i];
if(f[i] && d[ver] > d[t] + w[i]){
d[ver] = d[t] + w[i];
pre[ver] = i;
incf[ver] = min(f[i], incf[t]);
if(!st[ver]){
q[tt++] = ver;
if(tt == N) tt = 0;
st[ver] = true;
}
}
}
}
return incf[T] > 0;
}
int EK(){
int cost = 0;
while(spfa()){
int t = incf[T];
cost += t * d[T];
for(int i = T; i !=S; i = e[pre[i] ^ 1]){
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
return cost;
}
int main(){
cin>>n;
S = 0, T = n + 1;
memset(h, -1, sizeof h);
int tot = 0;
for(int i = 1; i <= n; i++){
cin>>s[i];
tot += s[i];
add(i, i < n ? i + 1 : 1, INF, 1);
add(i, i > 1 ? i - 1 : n, INF, 1);
}
tot /= n;
for(int i = 1; i <= n; i++){
if(tot < s[i]) add(S, i, s[i] - tot, 0);
else if(tot > s[i]) add(i, T, tot - s[i], 0);
}
cout<<EK()<<endl;
return 0;
}