【网络流24题专题】5 · 费用流进阶

似乎是比较进阶的费用流问题。

分别是 loj#6013 负载平衡、loj#6122 航空路线 、 loj#6010 数字梯形 和 loj#6223 汽车加油行驶问题。

负载平衡

G 公司有 $ n $ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 $ n $ 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

$n\leq 100$。

一道个人感觉有点东西的建图题。首先不难发现这是个均分纸牌问题。这个贪心说实话我理解的还不够深入。于是考虑怎么建图。

首先不难想到,由于每个点最后都要回到平均值,即一部分点需要将值给出去,一部分需要接受,那么就应该是一个类二分图的样子。但问题在于,怎么添加流量和(可能有的)费用呢?一开始想的是两个点之间差值为 $k$ 的话就连 $f=k,c=1$ 的边,然后超级源和超级汇都连 $+\infty,0$ 的边。但是这样根本无法限制每个点的流量。

现在考虑思路化地去思考这道题。

首先考虑流量之于这一题是什么存在——流量即限制,那么此题的限制就在于每个点最多只要增/减 $|\overline{a}-a_i|$ 的值;费用就显然是 $1$ 了。

那么考虑怎么连边。注意到点之间怎么流,是没有限制的,也就是说限制流图的中部是错的。于是考虑限制流图的前部和后部,发现只需要让 $\rm S$ 连向每个 $a_i>\overline{a}$ 的点 $i$ ,容量为 $a_i-\overline{a}$ ;让每个 $a_j\leq \overline{a}$ 的点 $j$ 连向 $\rm T$ ,容量为 $\overline{a}-a_j$ 。中部的连法需要考虑实际意义,由于只要是相邻就可传递,所以直接向每个与自己相邻的点连边即可。

嗯,尤其需要注意的是,每个点都需要有一个替身(也就是需要拆点)。此处拆点的目的不再是限制了(因为自身和自身之间不连边),而是题目意义(每个点可以作为中介接受比自己小的点的转运)。

然后这里放一下新版的 MCMF 的板子吧。上面的都是好久之前写的了。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

typedef long long ll ;

const int N = 200010 ;
const int I = 998244353 ;

#define to(k) e[k].to
#define fr(k) e[k].from
#define fw(k) e[k].flow
#define ct(k) e[k].cost
#define next(k) e[k].next

struct Edge{
int to ;
int from ;
int flow ;
int cost ;
int next ;
}e[N * 2] ;

int _s ;
int _t ;
int ans ;
int res ;
int cnt ;
int n, m ;
int g[N] ;
int vis[N] ;
int dis[N] ;
int pre[N] ;
int head[N] ;
int _last[N] ;
queue <int> q ;

void add(int u, int v, int f, int c){
to(++ cnt) = v ;
next(cnt) = head[u] ;
fw(cnt) = f ; ct(cnt) = c ;
fr(cnt) = u ; head[u] = cnt ;
}
bool spfa(){
fill(g, g + n + 1, I) ;
fill(dis, dis + n + 1, I) ;
fill(vis, vis + n + 1, 0) ;
q.push(_s) ; vis[_s] = 1 ; dis[_s] = 0 ;
while (!q.empty()){
int x = q.front() ;
q.pop() ; vis[x] = 0 ;
for (int k = head[x] ; ~k ; k = next(k))
if (dis[to(k)] > dis[x] + ct(k) && fw(k)){
dis[to(k)] = dis[x] + ct(k) ;
g[to(k)] = min(fw(k), g[x]) ;
pre[to(k)] = x ; _last[to(k)] = k ;
if (!vis[to(k)]){
q.push(to(k)) ;
vis[to(k)] = 1 ;
}
}
}
return (bool)(dis[_t] < I) ;
}
void ek(){
while (spfa()){
int x = _t ;
res += g[_t] ;
ans += g[_t] * dis[_t] ;
//cout << g[_t] << " " << ans << endl ;
while (x != _s){
fw(_last[x]) -= g[_t] ;
fw(_last[x] ^ 1) += g[_t] ;
x = pre[x] ;
}
}
}

int _n ;
int sum ;
int bbar ;
int base[N] ;

int main(){
int u, v, f, c ;
cin >> _n ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= _n ; ++ i)
cin >> base[i], sum += base[i] ;
bbar = sum / _n ;
_s = 0, _t = 2 * _n + 1 ;
add(1, _n, I, 1) ;
add(_n, 1, 0, -1) ;
add(1, 2 * _n, I, 1) ;
add(2 * _n, 1, 0, -1) ;
add(_n, 1, I, 1) ;
add(1, _n, 0, -1) ;
add(_n, 1 + _n, I, 1) ;
add(1 + _n, _n, 0, -1) ;
for (int i = 1 ; i <= _n ; ++ i){
if (i > 1){
add(i, i - 1, I, 1) ;
add(i - 1, i, 0, -1) ;
add(i, i + _n - 1, I, 1) ;
add(i + _n - 1, i, 0, -1) ;
}
if (i < _n){
add(i, i + 1, I, 1) ;
add(i + 1, i, 0, -1) ;
add(i, i + _n + 1, I, 1) ;
add(i + _n + 1, i, 0, -1) ;
}
if (base[i] > bbar){
add(i, _s, 0, 0) ;
add(_s, i, base[i] - bbar, 0) ;
}
else {
add(_t, i + _n, 0, 0) ;
add(i + _n, _t, - base[i] + bbar, 0) ;
}
}
//cout << cnt << endl ;
/*
for (int k = 0 ; k <= cnt ; ++ k)
cout << fr(k) << " " << to(k) << " " << fw(k) << " " << ct(k) << endl ;
*/
n = _t + 1 ; ek() ;
cout << ans << endl ;
}

航空路线问题

给定一张航空图,图中顶点代表城市,边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

  1. 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。
  2. 除起点城市外,任何城市只能访问一次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

对于所有数据,$n < 100$

其实这题不是很难。但是好像很多题解不是很负责任,于是自己写了一下Sol表示想要d其他题解(雾

感觉是个很妙(感觉自己应该会,但是就是想不起来)的转化,就是如果让找一条从 $1$ 出发经过 $n$ 回到 $1$ 的无重复点回路,那本质就是在找两条 $1$ 到 $n$ 的不相交路径。


说一点实现上的小细节吧。主要内容是「跟其他题解不一样的东西」。

发现大家在做这个题的时候,都是特判的「是否存在一条直接连通 $1$ 和 $n$」 的路径,然后直接输出。首先这么做,较为麻烦(虽然也就只多了一两二三行),其次正确性有待考究。

这个地方就需要思考,为什么大家的实现需要特判这个细节?原因是假设只有 $1\leftrightarrow n$ 这一条边,那么这条路需要走两次。但是连边 $(u,v)$ 的时候大家都是写的 add(u',v,1,0),导致只能走一次。个人认为,由于这是个基础题,所以每个细节都需要写的十分合理,但这个地方显然就不合理。

网络流题讲究对着限制找flow,对着代价找cost。这个题目里显然只限制了一个点至多走一次,但是没限制一条边至多走一次——虽然本质上,没啥很大区别,因为点至多一次决定了边至多一次——但是这从某种程度上决定了对这个题建模的理解程度。所以我认为,为了更好地实现「网络流24题」的网络流教学任务,应该在连边 $(u,v)$ 时如是写:

1
add(u',v,Inf,0)

这样有两个好处:

1、只需要特判无解,根本不需要那些无聊的判来判去判流量多少,影响代码的美观和简练。

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
int main(){
cnt = -1 ;
cin >> _n >> _m ;
x = _n * 2 ; y = 1 + _n ;
_s = 0 ; _t = _n + _n + 1 ;
memset(head, -1, sizeof(head)) ;
add(_s, 1, 2, 0) ; add(x, _t, 2, 0) ;
add(1, y, 2, -1) ; add(_n, x, 2, -1) ;
for (int i = 1 ; i <= _n ; ++ i)
cin >> s, rt[t[s] = i] = s ;
for (int i = 1 ; i <= _n ; ++ i)
add(i, i + _n, 1, -1) ;
for (int i = 1 ; i <= _m ; ++ i){
cin >> s >> ss ;
int p = t[s] ;
int q = t[ss] ;
if (p > q) swap(p, q) ;
//cout << p << " " << q << endl ;
add(p + _n, q, I, 0) ;
}
buc[1] = 1 ;
n = _t + 1 ; ek() ;
if (!ret)
return puts("No Solution!"), 0 ;
cout << -res - 2 << endl ;
dfs(1, l) ; cout << rt[1] << endl ;
for (int i = 0 ; i < l ; ++ i)
cout << rt[ans[i]] << '\n' ; l = 0 ;
for (int i = 0 ; i <= cnt ; ++ i)
if (ct(i) == -1 && !fw(i) && !buc[fr(i)])
ans[++ l] = fr(i) ;
sort(ans + 1, ans + l + 1, comp) ;
for (int i = 1 ; i <= l ; ++ i)
cout << rt[ans[i]] << '\n' ;
return cout << rt[1] << endl, 0 ;
}

btw,其实只需要dfs一遍即可。由于访问过程一定是单调的,所以将走完一遍后那些没走过的节点排序输出即可。


然后需要注意的是,由于本身 $1$ 和 $n$ 都可以经过多次,所以和自己的替身连边要连 $f=2$ 的。

哦,对了,这题其实跟「双调巡游(bitonic tour)」差不多,唯独就是找的不是哈密顿回路且不保证是完全图。多加一维枚举和 $i,j$ 连通的点即可。

数字梯形问题

给定一个 $n$ 行的数字梯形,从第一行到最后一行分别有 $2,3,\cdots,n+1$ 个数字。每个数字可以向左下或者右下第一个数字的地方移动。求:

1、$m$ 条互不相交路径的数值最大总和;

2、$m$ 条可以存在点相交时的路径数值最大总和;

3、$m$ 条可以存在点相交或者边相交时的路径数值最大总和;

第一问 · 完全不相交的路径

发现本质上,就是最小权路径覆盖问题。那么常规做法是,限制选的次数要通过限制流量来模拟,但是一个单点不存在流量,所以需要拆点。

大概就是每个点拆成两个点,然后对于某个点和它的副本连一条 $f=1,c=-base[x]$ 的边表示选了,毕竟是求最大值。然后 $\rm S$ 和最顶上的连 $f=1,c=0$ 的边,$\rm T$ 和最下面一层连 $f=1,c=0$,原图中点 $i,j$ 相连用 $i’\to j$ 刻画即可。

第二问 · 边不相交的路径

我们考虑此时其实是删除了每个点被选取次数的限制。那么我们就将每个点和自己的副本之间的边容量改成$+ \infty$,并把 $\rm T$ 与最底下的所有点的容量扩为 $+ \infty$ 即可。注意后半部分的扩容,其目的在于防止中间节点的扩容被限制

第三问 · 随便的路径

既然都随便了,就直接把所有的边都设置成$+ \infty$,但是显然的是我们不能扩 $\rm S$ 连出去的边。这样就永远保证了,从 $\rm S$ 走出来一定是一系列链,而不是一个类树形图。

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
int L1, R1, L ;
int main(){
memset(head, -1, sizeof(head)) ;
cin >> M >> N ; S = 0, T = 1 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j < M + i ; ++ j)
cin >> base[i][j], Id[i][j] = (tot += 2) ;
for (i = 1 ; i <= M ; ++ i) Add(S, Id[1][i], 1, 0) ; L = cnt + 1 ;
for (L1 = cnt + 1, i = 1 ; i <= N + M ; ++ i) Add(Id[N][i] + 1, T, 1, 0) ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j < M + i ; ++ j)
Add(Id[i][j], Id[i][j] + 1, 1, -base[i][j]) ; R1 = cnt ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j < M + i ; ++ j)
if (i < N) Add(Id[i][j] + 1, Id[i + 1][j], 1, 0), Add(Id[i][j] + 1, Id[i + 1][j + 1], 1, 0) ;
MCMF() ; cout << -Ans << endl ;
for (i = 0 ; i <= cnt ; ++ i) E[i].f = t[i] ;
for (i = L1 ; i < R1 ; i += 2) E[i].f = Inf ;
for (i = L1 + 1 ; i <= R1 ; i += 2) E[i].f = 0 ;
MCMF() ; cout << -Ans << endl ;
for (i = 0 ; i <= cnt ; ++ i) E[i].f = t[i] ;
for (i = L ; i < cnt ; i += 2) E[i].f = Inf ;
for (i = L + 1 ; i <= cnt ; i += 2) E[i].f = 0 ;
MCMF() ; cout << -Ans << endl ; return 0 ;
/* 以下是错误的建边
for (i = 1 ; i <= M ; ++ i)
cin >> base[++ tot], Add(S, tot, 1, -base[tot]) ;
for (i = 1 ; i < N ; ++ i)
for (j = 1 ; j <= M + i ; ++ j){
cin >> base[++ tot] ; int sd = (2 * M + i - 2) * (i - 1) / 2 + 1 ;
for (int k = sd ; k <= (2 * M + i - 1) * i / 2 ; ++ k) Add(k, tot, + Inf, -base[tot]) ;
}
for (T = tot + 1, i = tot - (N + M - 1) + 1 ; i <= tot ; ++ i) Add(i, T, 1, 0) ; ++ tot, MCMF() ; cout << -Ans << endl ; */
/*MCMF() ; cout << -Ans << endl ; */
}

汽车加油行驶问题

给定一个 $\text{N}\times \text{N}$ 的方形网格,设其左上角为起点◎,坐标为 $\text{(1,1)} $ ,$\text{X}$ 轴向右为正, $\text{Y}$ 轴向下为正,每个方格边长为 1 ,如图所示。

一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 $(\text{N},\text{N})$ 。

在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

  • 汽车只能沿网格边行驶,装满油后能行驶 $\text{K}$ 条网格边。
  • 出发时汽车已装满油,在起点与终点处不设油库。
  • 汽车经过一条网格边时,若其 $\text{X}$ 坐标或 $\text{Y}$ 坐标减小,则应付费用 $\text{B}$ ,否则免付费用。
  • 汽车在行驶过程中遇油库则应加满油并付加油费用 $\text{A} $。
  • 在需要时可在网格点处增设油库,并付增设油库费用 $\text{C} $ (不含加油费用 $\text{A} $ )。
  • $\rm N , K , A , B , C$ 均为正整数, 且满足约束: $2\leq \text{N} \leq 100, 2 \leq \text{K} \leq 10$。

设计一个算法,求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

233

这题第一眼看上去条件很多。考虑状态的设计。发现对于每个状态 $(i,j)$ ,当前的油量 $k$ 都决定了每一步的决策,所以不难看出应该把 $k$ 也放到状态里形成分层图。那么就直接模拟一下走的过程,按分层图建图,流一下即可。

然而此题就是考了个分层图。因为本身所有边流量都是 $1$,所以费用流就是在做最短路233

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
int main(){
cnt = -1 ;
cin >> N >> K >> A >> B >> C ;
memset(head, -1, sizeof(head)) ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j){
cin >> Ma[i][j] ;
for (k = 0 ; k <= K ; ++ k) Id[i][j][k] = ++ tot ;
}
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j)
if (Ma[i][j])
for (k = 0 ; k < K ; ++ k){
if (i < N) Add(Id[i][j][k], Id[i + 1][j][K - 1], 1, A) ;
if (j < N) Add(Id[i][j][k], Id[i][j + 1][K - 1], 1, A) ;
if (i > 1) Add(Id[i][j][k], Id[i - 1][j][K - 1], 1, A + B) ;
if (j > 1) Add(Id[i][j][k], Id[i][j - 1][K - 1], 1, A + B) ;
}
else {
for (k = 0 ; k < K ; ++ k) Add(Id[i][j][k], Id[i][j][K], 1, A + C) ;
for (k = 1 ; k <= K ; ++ k){
if (i < N) Add(Id[i][j][k], Id[i + 1][j][k - 1], 1, 0) ;
if (j < N) Add(Id[i][j][k], Id[i][j + 1][k - 1], 1, 0) ;
if (i > 1) Add(Id[i][j][k], Id[i - 1][j][k - 1], 1, B) ;
if (j > 1) Add(Id[i][j][k], Id[i][j - 1][k - 1], 1, B) ;
}
}
S = 0, T = tot + 1, Add(S, Id[1][1][K], 1, 0) ;
for (i = 0 ; i <= K ; ++ i) Add(Id[N][N][i], T, 1, 0) ;
MFMC() ; cout << Ans << endl ; return 0 ;
}