最小费用流

ACM

积累一下最小费用流的模板
固定流量的最小费用流只要在维护流量的时候不断的减少就行了。
感觉链式前星星有的时候不能够被替代，因为有时候需要维护边的属性

最小费用最大流的模板

首先对每一天边的费用求最短路。
因为边的费用可能是负的，所以必须要用Bellman-ford或者是SPFA算法。
对其中的一些变量进行相应的说明：

pre[]:记录的是前面的边的编号
反向边的flow是负值，因此即使反向边的cap=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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
int s, t, n, m;
struct Edge{
    int v, cost, cap, next, flow;
}edge[maxm];
int head[maxn];
int pre[maxn];//记录的是哪一条边的编号
int tot;
int dis[maxn];
bool vis[maxn];
void init(){
    memset(pre, -1, sizeof(pre));
    memset(head, -1, sizeof(head));
    tot = 0;
}
void add_edge(int u, int v, int weight, int price){
    edge[tot].v = v;
    edge[tot].cost = price;
    edge[tot].cap = weight;
    edge[tot].flow = 0;
    edge[tot].next = head[u];
    head[u] = tot++;
    edge[tot].v = u;
    edge[tot].cost = -1*price;
    edge[tot].cap = 0;
    edge[tot].flow = 0;
    edge[tot].next = head[v];
    head[v] = tot++;
}
bool SPFA(int s, int t){
    for(int i=0; i<maxn; i++) dis[i] = INF;
    dis[s] = 0;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    vis[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i=head[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(edge[i].cap>edge[i].flow && dis[v]>dis[u]+edge[i].cost){
                dis[v] = dis[u]+edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    if(pre[t] == -1) return false;
    return true;
}
int min_cost_max_flow(int s, int t, int &min_cost){
    int flow = 0;
    while(SPFA(s, t)){
        int Min = INF;
        for(int i = pre[t]; ~i; i = pre[edge[i^1].v]){
            if(Min>edge[i].cap-edge[i].flow){
                Min = edge[i].cap - edge[i].flow;
            }
        }
        for(int i=pre[t]; ~i; i = pre[edge[i^1].v]){
            //cout<<edge[i^1].v<<" ";
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            min_cost += edge[i].cost*Min;
        }
        flow += Min;
    }
    return flow;
}
int main(){
    while(cin>>n>>m>>s>>t){
        init();
        int u, v, price, weight;
        for(int i=0; i<m; i++){
            cin>>u>>v>>price>>weight;
            add_edge(u, v, weight, price);
        }
        int min_cost = 0;
        int ans = min_cost_max_flow(s, t, min_cost);
        cout<<min_cost<<" "<<ans<<endl;
    }
    return 0;
}
/*
5 7 0 4
0 1 2 10
1 2 6 6
0 2 4 2
1 3 2 6
3 2 3 3
2 4 2 5
3 4 6 8
*/

模板题目

poj2135

题意

从起点1到N，然后再从N回到1，每一条边最多经过一次。边有长度，问最小需要走过的长度。

题解

将边的长度作为边的花费，然后每一条边只能经过一次就设边的容量为1.
设一个超级源S与1节点连接，边的容量为2， 费用为0，
超级汇与N节点连接，边的容量为2， 费用为0.

AC代码

上面的模板代码只要改一改就可以了

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
107
108
109
110
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e4+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
int s, t, n, m;
struct Edge{
    int v, cost, cap, next, flow;
}edge[maxm];
int head[maxn];
int pre[maxn];//记录的是哪一条边的编号
int tot;
int dis[maxn];
bool vis[maxn];
void init(){
    memset(pre, -1, sizeof(pre));
    memset(head, -1, sizeof(head));
    tot = 0;
}
void add_edge(int u, int v, int weight, int price){
    edge[tot].v = v;
    edge[tot].cost = price;
    edge[tot].cap = weight;
    edge[tot].flow = 0;
    edge[tot].next = head[u];
    head[u] = tot++;
    edge[tot].v = u;
    edge[tot].cost = -1*price;
    edge[tot].cap = 0;
    edge[tot].flow = 0;
    edge[tot].next = head[v];
    head[v] = tot++;
}
bool SPFA(int s, int t){
    for(int i=0; i<maxn; i++) dis[i] = INF;
    dis[s] = 0;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    vis[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i=head[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(edge[i].cap>edge[i].flow && dis[v]>dis[u]+edge[i].cost){
                dis[v] = dis[u]+edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    if(pre[t] == -1) return false;
    return true;
}
int min_cost_max_flow(int s, int t, int &min_cost){
    int flow = 0;
    while(SPFA(s, t)){
        int Min = INF;
        for(int i = pre[t]; ~i; i = pre[edge[i^1].v]){
            if(Min>edge[i].cap-edge[i].flow){
                Min = edge[i].cap - edge[i].flow;
            }
        }
        for(int i=pre[t]; ~i; i = pre[edge[i^1].v]){
            //cout<<edge[i^1].v<<" ";
            edge[i].flow += Min;
            edge[i^1].flow -= Min;
            min_cost += edge[i].cost*Min;
        }
        flow += Min;
    }
    return flow;
}
int main(){
    while(cin>>n>>m){
        init();
        int u, v, len;
        s = 0;
        t = 2001;
        for(int i=0; i<m; i++){
            cin>>u>>v>>len;
            add_edge(u, v, 1, len);
            add_edge(v, u, 1, len);
        }
        add_edge(s, 1, 2, 0);
        add_edge(n, t, 2, 0);
        int min_cost = 0;
        int ans = min_cost_max_flow(s, t, min_cost);
        cout<<min_cost<<endl;
    }
    return 0;
}

未解决的问题

本文标题:最小费用流

文章作者:Babydragon

发布时间:2018-04-28, 13:31:17

最后更新:2018-04-28, 20:47:30

原始链接:http://baolintian.github.io/2018/04/28/最小费用流/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 最小费用最大流的模板
  2. 2. 模板题目
    1. 2.1. 题意
    2. 2.2. 题解
    3. 2.3. AC代码
  3. 3. 未解决的问题
{{ live2d() }}