网络流-最小费用最大流学习笔记
# 最小费用最大流
问题同最大流，但每条路径都有一个价格，代表每单位流量经过此路径需要的费用。求最小费用最大流
# HDU 6118
特别说明：单路増广比多路増广更快，猜测原因：
- 増广时只对最短路进行増广，仅在存在多条最短路时才会多次増广。而该题的数据中此类情况较少。
- 我的多路増广实现太差
# 模板题 洛谷P3381
别人都能做到1.5s~我怎么就自带大常数呢？
# 单路増广 2.25s(已关闭流同步)
把long long换成int能快不少
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct EK{
const static ll inf = 0x7f7f7f7f7f7f7f7f;
const static int mx_edge = 5e4 + 1e3, mx_node = 5e3 + 1e2;
int head[mx_node], edge_cnt, n;
int pre_edge[mx_node], que[mx_node], q_head, q_tail; // 每个点连接前驱的边
bool in_queue[mx_node];
ll dist[mx_node], flow[mx_node];
struct E{int v, next; ll cap, cost;} edge[2 * mx_edge];
void init(int nx){
n = nx; edge_cnt = 0;
for(int i=0; i<=n; i++) head[i] = -1;
}
void add_edge(int u, int v, ll cap, ll cost){
edge[edge_cnt] = {v, head[u], cap, cost}; head[u] = edge_cnt++;
edge[edge_cnt] = {u, head[v], 0, -cost}; head[v] = edge_cnt++;
}
bool spfa(int s, int t){
for(int i=0; i<=n; i++) dist[i] = inf;
q_head = q_tail = 0; que[q_tail++] = s;
in_queue[s] = 1, dist[s] = 0, pre_edge[t] = -1, flow[s] = inf;
while(q_head ^ q_tail){
int now = que[q_head++];
q_head %= mx_node;
in_queue[now] = 0;
for(int i=head[now], v; ~i; i=edge[i].next){
if(edge[i].cap <= 0) continue;
v = edge[i].v;
if(dist[v] > dist[now] + edge[i].cost){
dist[v] = dist[now] + edge[i].cost;
pre_edge[v] = i;
flow[v] = min(flow[now], edge[i].cap);
if(!in_queue[v]){
in_queue[v] = 1;
que[q_tail++] = v;
q_tail %= mx_node;
}
}
}
}
return pre_edge[t] != -1;
}
pair<ll, ll> dinic(int s, int t){
for(int i=0; i<=n; i++) in_queue[i] = false;
ll mx_flow = 0, cost = 0;
while(spfa(s, t)){
int now = t;
mx_flow += flow[t];
cost += flow[t] * dist[t];
while(now != s){
edge[pre_edge[now]].cap -= flow[t];
edge[pre_edge[now] ^ 1].cap += flow[t];
now = edge[pre_edge[now] ^ 1].v;
}
}
return {mx_flow, cost};
}
} max_flow_min_cost;
signed main(){
int n, m, s, t, u, v, w, f;
cin >> n >> m >> s >> t;
max_flow_min_cost.init(n + 50);
for(int i=0; i<m; i++){
cin >> u >> v >> w >> f;
max_flow_min_cost.add_edge(u, v, w, f);
}
pair<ll, ll> ans = max_flow_min_cost.dinic(s, t);
cout << ans.first << " " << ans.second << endl;
}
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
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
# 多路増广 2.06s(已关闭流同步)
把long long换成int能快不少(1.79s)
dfs前重置数组cur，该数组似乎只优化u=s的情况，对于u!=s，要么该节点已经被访问过了(vis[u]=1)，要么cur[u]=head[u]
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Dinic{
const static ll inf = 0x7f7f7f7f7f7f7f7f;
const static int mx_edge = 5e4 + 1e3, mx_node = 5e3 + 1e2;
int head[mx_node], edge_cnt, n;
int cur[mx_node], que[mx_node], q_head, q_tail;
bool in_queue[mx_node], vis[mx_node], extend_success;
ll dist[mx_node], mx_flow, mn_cost;
struct E{int v, next; ll cap, cost;} edge[2 * mx_edge];
void init(int nx){
n = nx; edge_cnt = 0;
for(int i=0; i<=n; i++) head[i] = -1;
}
void add_edge(int u, int v, ll cap, ll cost){
edge[edge_cnt] = {v, head[u], cap, cost}; head[u] = edge_cnt++;
edge[edge_cnt] = {u, head[v], 0, -cost}; head[v] = edge_cnt++;
}
bool spfa(int s, int t){ // 计算从s到每个节点的最短路
for(int i=0; i<=n; i++) dist[i] = inf;
q_head = q_tail = 0; que[q_tail++] = s;
in_queue[s] = 1, dist[s] = 0;
while(q_tail ^ q_head){ // 手工队列
int now = que[q_head++];
q_head %= mx_node;
in_queue[now] = 0;
for(int i=head[now], v; ~i; i=edge[i].next){
if(edge[i].cap <= 0) continue;
v = edge[i].v;
if(dist[v] > dist[now] + edge[i].cost){
dist[v] = dist[now] + edge[i].cost;
if(!in_queue[v]){
in_queue[v] = 1;
que[q_tail++] = v;
q_tail %= mx_node;
}
}
}
}
return dist[t] != inf; // 判断t是否可达
}
ll dfs(int u, int t, ll lim){
vis[u] = true;
if(u == t) {
extend_success = true;
mx_flow += lim;
mn_cost += dist[u] * lim;
return lim;
}
ll ret = 0, tmp;
for(int &i=cur[u], v; ~i; i=edge[i].next){
v = edge[i].v;
if(dist[u] + edge[i].cost == dist[v] && edge[i].cap > 0 && (!vis[v] || v==t)){ // 如果是最短路径、流量为正且未访问过(t除外)
tmp = dfs(v, t, min(lim-ret, edge[i].cap));
if(tmp > 0){
ret += tmp;
edge[i].cap -= tmp;
edge[i^1].cap += tmp;
if(ret >= lim) break;
}
}
}
return ret;
}
pair<ll, ll> dinic(int s, int t){
for(int i=0; i<=n; i++) in_queue[i] = false;
mx_flow = 0, mn_cost = 0;
while(spfa(s, t)){
for(int i=0; i<=n; i++) vis[i] = false;
for(int i=0; i<=n; i++) cur[i] = head[i];
extend_success = true; // dfs拓展是否成功
while(extend_success) extend_success = false, dfs(s, t, inf);
}
return {mx_flow, mn_cost};
}
} max_flow_min_cost;
signed main(){
int n, m, s, t, u, v, w, f;
cin >> n >> m >> s >> t;
max_flow_min_cost.init(n + 50);
for(int i=0; i<m; i++){
cin >> u >> v >> w >> f;
max_flow_min_cost.add_edge(u, v, w, f);
}
pair<ll, ll> ans = max_flow_min_cost.dinic(s, t);
cout << ans.first << " " << ans.second << endl;
}
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
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
# ZKW费用流
稠密图中表现良好，稀疏图中还不如SPFA最短路
待补充
上次更新: 2021/02/24, 03:37:30