【网络流24题专题】1 · 较简单的费用流

包括以下可以用费用流解决的问题:

loj#6011 运输问题,loj#6012 分配问题 、 loj#6024 深海机器人问题 以及 loj#6025 火星运输问题。

运输问题

给定一个二分图。一开始每个点有点权,对于一条边所连接的 $a_i,b_j$ ,可以让 $a_i\text{+=}\Delta,b_j\text{-=}\Delta$ 或者反过来,代价均为 $c_{i,j}\times \Delta$。现在需要让 $\sum a_i=\sum b_i$ ,最小化代价和。

看了 $40\%$ ?

其实就是

其中$i$代表仓库的编号,$j$代表商店的编号,建完图跑费用流即可。

由于SPFA死了,所以就一直用$dijk$做费用流,只不过难背一点……然后第二问的话就把权值取负重新做一下费用流就好。

总结一下,这个题似乎是比较裸的费用流的题了?一般费用流大概都是用来求解最优化问题的吧qwq……

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
struct Edge{
int to, next, f, c ;
}E[MAXN] ; int head[MAXN], cnt = -1 ;
int S, T, N, M, dist[MAXN], i, j, k, t[MAXN], x ;
struct node{
int dist, num ;
bool operator <(const node & now) const{return dist > now.dist ; }
}; priority_queue<node> q ; bool vis[MAXN] ; int Last[MAXN], F[MAXN], H[MAXN], Pre[MAXN], MAX_C ;

inline void Add(const int &u, const int &v, const int &f, const int& c){
E[++ cnt].to = v, E[cnt].c = c, t[cnt] = f ;
E[cnt].f = f, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].c = -c, t[cnt] = 0 ;
E[cnt].f = 0, E[cnt].next = head[v], head[v] = cnt ;
}
inline bool dijkstra(){
q.push((node){0, S}) ; vis[S] = dist[S] = 0, F[0] = Inf ;
for (i = 1 ; i <= T ; ++ i) dist[i] = F[i] = Inf, vis[i] = 0 ;
while (!q.empty()){
node now = q.top() ; q.pop() ;
int fr = now.num, sec = now.dist ; if (vis[fr]) continue ;
for (vis[fr] = 1, k = head[fr] ; k != -1 ; k = E[k].next){
int nowc = sec + E[k].c + H[fr] - H[to(k)] ;
if (E[k].f > 0 && !vis[to(k)] && dist[to(k)] > nowc){
dist[to(k)] = nowc, q.push((node){dist[to(k)], to(k)}) ;
F[to(k)] = min(F[fr], E[k].f), Pre[to(k)] = fr, Last[to(k)] = k ;
}//!!!!!
}
}
return dist[T] < Inf ;
}
void MCMF(int qwq){
int _Ed ; MAX_C = 0 ;
while (dijkstra()){
_Ed = T, MAX_C += (dist[T] - H[S] + H[T]) * F[T] ;
while(_Ed != S) E[Last[_Ed]].f -= F[T], E[Last[_Ed] ^ 1].f += F[T], _Ed = Pre[_Ed] ;
for (i = 0 ; i <= T ; ++ i) H[i] += dist[i] ; /* cout << MAX_C << endl ; */
}
cout << MAX_C * qwq << endl ;
}
int main(){
cin >> N >> M, S = 0 ;
T = N + M + 1, memset(head, -1, sizeof(head)) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &x), Add(S, i, x, 0) ;
for (i = N + 1 ; i <= N + M ; ++ i) scanf("%d", &x), Add(i, T, x, 0) ;
for (i = 1 ; i <= N ; ++ i)
for (j = N + 1 ; j <= N + M ; ++ j)
scanf("%d", &x), Add(i, j, Inf, x) ;
// for (i = 0 ; i <= cnt ; ++ i) printf("%d %d %d\n", E[i].to + 1, E[i].f, E[i].c) ;
MCMF(1) ; for (i = 0 ; i <= cnt ; ++ i) E[i].f = t[i], E[i].c = -E[i].c ; MCMF(-1) ; return 0 ;
}

分配问题

两个部均为 $n$ 个点的最大权二分图完美匹配匹配问题。

可能会存在一个神奇的KM算法。但是自己不会x

发现此题中不仅需要最大权,也需要完美匹配。所以直接跑最小费用/最大费用最大流即可。

细节的话,考虑直接在二分图匹配的流图基础上,加上 $c_{i,j}$ 的费用就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
此处是dijkstra……
void MCMF(int qwq){
int _Ed ; MAX_C = 0 ;
while (dijkstra()){
_Ed = T, MAX_C += (dist[T] - H[S] + H[T]) * F[T] ;
while(_Ed != S)
E[Last[_Ed]].f -= F[T], E[Last[_Ed] ^ 1].f += F[T], _Ed = Pre[_Ed] ;
for (i = 0 ; i <= T ; ++ i) H[i] += dist[i] ; /* cout << MAX_C << endl ; */
}
cout << MAX_C * qwq << endl ;
}
int main(){
memset(head, -1, sizeof(head)) ;
cin >> N ; S = 0, T = N << 1 | 1 ;
for (i = 1 ; i <= N ; ++ i) Add(S, i, 1, 0) ;
for (i = N + 1 ; i <= N + N ; ++ i) Add(i, T, 1, 0) ;
for (i = 1 ; i <= N ; ++ i)
for (j = N + 1 ; j <= N + N ; ++ j)
cin >> x, Add(i, j, Inf, x) ;
MCMF(1) ;
for (i = 0 ; i <= cnt ; ++ i)
E[i].c = -E[i].c, E[i].f = t[i] ;
MCMF(-1) ; return 0 ;
}

火星探险问题

火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本,每一块岩石标本由最先遇到它的探测车完成采集,每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。

本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。

用一个 $\text{P}\times \text{Q}$ 网格表示登陆舱与传送器之间的位置。登陆舱的位置在 $(X_1,Y_1)$ 处,传送器 的位置在 $(X_P,Y_Q)$ 处。 给定每个位置的状态,计算探测车的最优移动方案,使到达传送器的探测车的数量最多, 而且探测车采集到的岩石标本的数量最多。

233

发现每个点虽然可能有至多 $1$ 个石块,但是可以重复经过。于是自然想到把每个点拆成俩,之间连 $f=1,c=-1$ 的边。对于一个点 $x$ 和他直接连通的点 $y$ ,将 $x,x’$ 和 $y,y’$ 这 $2*2=4$ 个点对分别连 $f=\infty,c=0$ 的普通边,代表着走还是不走。当然这个地方还有另一个处理方法,就是直接拿 $x’$ 去跟 $y$ 连,然后每个 $x$ 再和 $x’$ 连一个 $f=\infty,c=0$ 的边。可以知道这样是本质相同的。

最后 $dfs$ 输出方案。这里 $dfs$ 的方式对我自己而言是有启发的。本来想的是逐渐增加 $\rm S$ 的初始流量,然后去 $dfs$ 找哪些边已经满流了。但这样没法去记录哪些是这一层增广的,哪些是之前增广的。所以考虑一开始全部流一下,然后边 $dfs$ 边模拟流的过程。判断每条边是否应该被流,直接看反向边的流量即可。

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
int num ;
int tot ;
int fl[M] ;
int ans[M] ;
int Id[N][N] ;
int base[N][N] ;
int _n, _m, _k ;

void dodo(int x, int y, int len){
//cout << x << " " << y << endl ;
if (x == _n && y == _m){
for (int i = 1 ; i < len ; ++ i)
cout << num << " " << ans[i] << '\n' ;
return ;
}
int now = Id[x][y] ;
for (int k = head[now] ; ~k ; k = next(k)){
if (fl[k] >= fw(k ^ 1))
continue ; else fl[k] ++ ;
if (to(k) == Id[x + 1][y])
{ ans[len] = 0 ; dodo(x + 1, y, len + 1) ; return ; }
if (to(k) == Id[x][y + 1])
{ ans[len] = 1 ; dodo(x, y + 1, len + 1) ; return ; }
if (to(k) == Id[x + 1][y] + tot)
{ ans[len] = 0 ; dodo(x + 1, y, len + 1) ; return ; }
if (to(k) == Id[x][y + 1] + tot)
{ ans[len] = 1 ; dodo(x, y + 1, len + 1) ; return ; }
}
now += tot ;
for (int k = head[now] ; ~k ; k = next(k)){
if (fl[k] >= fw(k ^ 1))
continue ; else fl[k] ++ ;
if (to(k) == Id[x + 1][y])
{ ans[len] = 0 ; dodo(x + 1, y, len + 1) ; return ; }
if (to(k) == Id[x][y + 1])
{ ans[len] = 1 ; dodo(x, y + 1, len + 1) ; return ; }
if (to(k) == Id[x + 1][y] + tot)
{ ans[len] = 0 ; dodo(x + 1, y, len + 1) ; return ; }
if (to(k) == Id[x][y + 1] + tot)
{ ans[len] = 1 ; dodo(x, y + 1, len + 1) ; return ; }
}
}
int main(){
cnt = -1 ;
int a, b, c, d ;
cin >> _k >> _m >> _n ;
for (int i = 0 ; i <= _n + 1 ; ++ i)
for (int j = 0 ; j <= _m + 1 ; ++ j)
base[i][j] = 1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= _n ; ++ i)
for (int j = 1 ; j <= _m ; ++ j)
cin >> base[i][j], Id[i][j] = ++ tot ;
n = _t = tot * 2 + 1 ; _s = 0 ;
add(_s, 1, _k, 0) ;
//add(_s, tot + 1, _k, 0) ;
//add(Id[_n][_m], _t, _k, 0) ;
add(Id[_n][_m] + tot, _t, _k, 0) ;
for (int i = 1 ; i <= _n ; ++ i)
for (int j = 1 ; j <= _m ; ++ j){
if (base[i][j] == 1) continue ;
if (base[i + 1][j] != 1){
add(Id[i][j], Id[i + 1][j], I, 0) ;
add(Id[i][j], Id[i + 1][j] + tot, I, 0) ;
add(Id[i][j] + tot, Id[i + 1][j], I, 0) ;
add(Id[i][j] + tot, Id[i + 1][j] + tot, I, 0) ;
}
if (base[i][j + 1] != 1){
add(Id[i][j], Id[i][j + 1], I, 0) ;
add(Id[i][j], Id[i][j + 1] + tot, I, 0) ;
add(Id[i][j] + tot, Id[i][j + 1], I, 0) ;
add(Id[i][j] + tot, Id[i][j + 1] + tot, I, 0) ;
}
if (base[i][j] == 2)
add(Id[i][j], Id[i][j] + tot, 1, -1) ;
//add(Id[i][j], Id[i][j] + tot, I, 0) ;
}
ek() ; //cout << res << endl ;
for (int i = 1 ; i <= _k ; ++ i)
num = i, dodo(1, 1, 1) ; return 0 ;
}

深海机器人问题

深海资源考察探险队的潜艇将到达深海的海底进行科学考察。潜艇内有多个深海机器人。潜艇到达深海海底后,深海机器人将离开潜艇向预定目标移动。深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。

本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。用一个 $\text{P} \times \text{Q}$ 网格表示深海机器人的可移动位置。西南角的坐标为 $(0,0)$ ,东北角的坐标为 $(Q,P)$ 。

给定每个深海机器人的出发位置和目标位置,以及每条网格边上生物标本的价值。计算深海机器人的最优移动方案, 使深海机器人到达目的地后,采集到的生物标本的总价值最高。

233

发现…似乎和上一道题差不多?唯一的区别就是权放到边上了,大概是24题里最简单的题之一了吧?

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
int main(){
cnt = -1 ;
int a, b, c, d ;
cin >> a >> b >> _n >> _m ;
memset(head, -1, sizeof(head)) ;
for (int i = 0 ; i <= _n ; ++ i)
for (int j = 0 ; j <= _m ; ++ j)
Id[i][j] = ++ tot ;
for (int i = 0 ; i <= _n ; ++ i)
for (int j = 0 ; j < _m ; ++ j)
cin >> c, add(Id[i][j], Id[i][j + 1], 1, -c) ;
for (int i = 0 ; i <= _m ; ++ i)
for (int j = 0 ; j < _n ; ++ j)
cin >> d, add(Id[j][i], Id[j + 1][i], 1, -d) ;
n = _t = tot + 1 ; _s = 0 ;
for (int i = 0 ; i <= _n ; ++ i)
for (int j = 0 ; j <= _m ; ++ j){
if (i < _n) add(Id[i][j], Id[i + 1][j], I, 0) ;
if (j < _m) add(Id[i][j], Id[i][j + 1], I, 0) ;
}
for (int i = 1 ; i <= a ; ++ i)
cin >> _k >> c >> d, add(_s, Id[c][d], _k, 0) ;
for (int i = 1 ; i <= b ; ++ i)
cin >> _k >> c >> d, add(Id[c][d], _t, _k, 0) ;
ek() ; cout << -res << endl ; return 0 ;
}

然后谷的讨论区快笑死我了: