【网络流24题专题】4 · 最大流模型进阶

包括以下稍微进阶一点的、可以用最大流解决的问题:

loj#6003 魔术球loj#6005 最长递增子序列loj#6015 星际转移.

魔术球问题

假设有 $n$ 根柱子,现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1, 2,3, . . .$ 的球。

(1) 每次只能在某根柱子的最上面放球。

(2) 在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 $n$ 根柱子上最多能放多少个球.

$n\leq 55$

考虑对于一组 $(i,j)$ ,如果 $i+j$ 是完全平方数,就由较小的那个向较大的那个连一条边。之后考虑本质上每根柱子上就是一个路径覆盖,所以持续加边,一直加到最小路径覆盖数 $> $ 柱子数为止。

有一个很有意思的性质,就是网络流可以在线加边并且不用考虑之前的决策。

这题真nm是写到吐血。板子也改了一下如果不完全连通时的写法,需要特判每个点是否连通。这题神烦的是需要一遍一遍地清空,然后边的编号很容易就写错。

最后zay教育我只需要二分就可以了,这样每次就可以把全部的边都加进去,这样就可以瞎清空。我太dd了。

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
#define to(k) e[k].to
#define fr(k) e[k].from
#define fw(k) e[k].flow
#define next(k) e[k].next

const int M = 100010 ;
const int N = 200010 ;
const double eps = 1e-9 ;

int cnt ;
int res ;
int n, m ;
int h[N] ;
int fa[N] ;
int gap[N] ;
int vis[N] ;
int _s, _t ;
int head[N] ;
int extra[N] ;
queue <int> q ;
struct ed{
int to ;
int from ;
int flow ;
int next ;
}e[N * 2] ;
struct state{
int h, num ;
bool operator <(const state & now)
const { return h < now.h ; }
} ;
priority_queue <state> p ;

void add(int a, int b, int c){
to(++ cnt) = b ;
fw(cnt) = c ; fr(cnt) = a ;
next(cnt) = head[a] ; head[a] = cnt ;
}
void bfs(){
q.push(_t) ;
while (!q.empty()){
int x = q.front() ; q.pop() ;
for (int k = head[x] ; ~k ; k = next(k))
if (h[to(k)] >= n + 1)
h[to(k)] = h[x] + 1, q.push(to(k)) ;
}
}
int HLPP(){
//cout << cnt << endl ;
h[_s] = 100000000 ; h[_t] = 0 ; bfs() ;
if (h[_s] >= 10000000) return extra[_t] ; else h[_s] = n ;
for (int k = head[_s] ; ~k ; k = next(k)){
extra[to(k)] += fw(k) ;
fw(k ^ 1) = fw(k), fw(k) = 0 ;
if (to(k) != _t && h[to(k)] <= n)
vis[to(k)] = 1, p.push((state){h[to(k)], to(k)}) ;
}
for (int i = 1 ; i <= n ; ++ i)
if (h[i] <= n + 1) gap[h[i]] ++ ;
while (!p.empty()){
state y = p.top() ;
int minh = 1000000000 ;
int x = y.num ; p.pop() ;
//cout << x << endl ;
if (h[x] == 100000000) break ; vis[x] = 0 ;
for (int k = head[x] ; ~k ; k = next(k)){
int val = min(fw(k), extra[x]) ;
if (val > 0 && h[to(k)] + 1 == h[x]){
fw(k) -= val ;
extra[x] -= val ;
fw(k ^ 1) += val ;
extra[to(k)] += val ;
if (to(k) == _s || to(k) == _t) continue ;
if (!vis[to(k)]) vis[to(k)] = 1,
p.push((state){h[to(k)], to(k)}) ;
}
if (!extra[x]) break ;
if (fw(k)) minh = min(minh, h[to(k)]) ;
}
if (extra[x] && minh<=n+1){
if (! -- gap[h[x]]){
for (int i = 1 ; i <= n ; ++ i)
if (i != _s && i != _t && h[i] > h[x] && h[i] < n + 1)
h[i] = n + 1 ;
}
gap[h[x] = minh + 1] ++ ; p.push((state){h[x], x}) ; vis[x] = 1 ;
}
}
return extra[_t] ;
}
int find(int x){
if (x == fa[x]) return x ; return fa[x] = find(fa[x]) ;
}
void output(int p){
for (int k = head[p] ; ~k ; k = e[k].next)
if (!fw(k) && to(k) != 2 && !(to(k) & 1))
printf(" %d", (to(k) - 2) / 2), output(to(k) - 1) ;
}
int main(){
cin >> m ;
_s = 1, _t = n = 2 ; cnt = -1 ;
h[1] = 1, h[2] = 0, head[1] = head[2] = -1 ;
for (res = 1 ; ; ++ res){
head[++ n] = -1 ;
h[n] = 100000000 ;
add(1, n, 1), add(n, 1, 0) ;
head[++ n] = -1 ;
h[n] = 100000000 ;
add(n, 2, 1), add(2, n, 0) ;
for (int j = 1 ; j < res ; ++ j)
if (sqrt(res + j) == (int)(sqrt(res + j)))
add(2 * j + 1, n, 1), add(n, 2 * j + 1, 0) ;
for (int i = 0 ; i <= n + 1 ; ++ i)
h[i] = 100000000, vis[i] = gap[i] = 0 ;
int ans = HLPP() ; if (res - ans > m) break ;
//cout << "--------------------" << endl ;
}
res -- ; cout << res << endl ;
for (int i = 1 ; i <= res ; ++ i) fa[i] = i ;
for (int i = 0 ; i <= cnt ; ++ i)
if (fr(i) > 1 && (fr(i) & 1) && !(to(i) & 1) && to(i) != 2 && !fw(i))
fa[find((to(i) - 2) / 2)] = find(fa[(fr(i) - 1) / 2]) ;
for (int i = 1 ; i <= res ; ++ i)
if (fa[i] == i) printf("%d", i), output(i * 2 + 1), puts("") ;
return 0 ;
}

最长递增子序列

给定正整数序列 $x_1 \ldots, x_n$。

1、计算其最长不下降子序列的长度 $s$。

2、如果每个元素只允许使用一次,计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。

3、如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$(其他元素仍然只允许使用一次),则从给定序列中最多可取出多少个不同的长度为 $s$ 的不下降子序列。

$n\leq 500$

考虑第一问可以直接拿来跑一个 $n^2$ 的 $dp$ 。对于第二问,考虑网络流。对于每个数,有限制只能用 $1$ 次,且必须要保证每个 LIS 长度都为 $s$ 。所以如果单纯地拿每个 $i$ 与起点和终点连边,对于一组 $i<j$ 且 $a_i<a_j$ 且 $f_j=f_{i}+1$ 的 $(i,j)$ ,中间连流量为 $1$ 的边。

这样建图就很有问题:

1、考虑这样建图,加谁一个点的入度为 $d_1$,出度为 $d_2$ ,那么实质上它会被使用 $\min\{d_1,d_2\}$ 次。为了防止这种情况出现,所以把一个点拆成两个点,一个点用来接收入度,一个点用来接收出度,$i\to i’$ 连流量为 $1$ 的边。

2、同时,由于并不能很容易地确定一条流经过多少条边,所以不是很容易得到长度为 $s$ 的 LIS。所以考虑换一种建图方式。即只让 $f_i=s$ 的每个 $i$ 与 $\rm T$ 连边。这样就保证走出来的只会是长度为 $s$ 的 LIS。

那么第三问,考虑再加上 $s\stackrel{f = +\infty}{\longrightarrow}1,1\stackrel{f = +\infty}{\longrightarrow}1’$ 这种边。如果 $f_n=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
36
int main(){
cin >> n ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
_s = 2 * n + 1, _t = 2 * n + 2 ;
for (int i = 1 ; i <= n ; ++ i)
cin >> base[i], f[i] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j < i ; ++ j)
if (base[j] <= base[i])
f[i] = max(f[i], f[j] + 1) ;
for (int i = 1 ; i <= n ; ++ i) res = max(res, f[i]) ;
for (int i = 1 ; i <= n ; ++ i)
add(i, i + n, 1), add(i + n, i, 0) ;
for (int i = 1 ; i <= n ; ++ i){
if (f[i] == 1) add(2 * n + 1, i, 1), add(i, 2 * n + 1, 0) ;
if (f[i] == res) add(i + n, 2 * n + 2, 1), add(2 * n + 2, i + n, 0) ;
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = i + 1 ; j <= n ; ++ j)
if (base[i] <= base[j] && f[i] + 1 == f[j])
add(i + n, j, 1), add(j, i + n, 0) ;
int t = n ; n = 2 * n + 2 ;
for (int i = 0 ; i <= n + 1 ; ++ i)
h[i] = 100000000, vis[i] = 0, gap[i] = 0 ;
cout << res << endl << HLPP() << endl ;
if (f[t] == res){
add(t, _t, 100000000), add(_t, t, 0) ;
add(t, t + t, 100000000), add(t + t, t, 0) ;
}
add(_s, 1, 100000000), add(1, _s, 0) ;
add(1, t + 1, 100000000), add(t + 1, 1, 0) ;
for (int i = 0 ; i <= n + 1 ; ++ i)
h[i] = 100000000, vis[i] = 0, gap[i] = 0 ;
if (t == 1) cout << 1 << endl ;
else cout << HLPP() << endl ; return 0 ;
}

星际转移

现有 $n$ 个太空站位于地球与月球之间,且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人,而每艘太空船 $i$ 只可容纳 $p_i$ 个人。每艘太空船将周期性地停靠一系列的太空站,例如:$\{1,3,4\}$ 表示该太空船将周期性地停靠太空站 134134134 …

每一艘太空船从一个太空站驶往任一太空站耗时均为 $1$。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上,太空船全在初始站。试设计一个算法,找出让所有人尽快地全部转移到月球上的运输方案。

$n,m\leq 50$ 。

很神奇的分层图建图。考虑本身似乎是路径规划问题,但是具有以下性质:1、边的限制跟网络流图的限制几乎相同;2、每条边的代价都是 $1$ ; 3、数据范围 $n,m\leq 50$ ,可以知道如果有解,最多就是在 $0\to -1$ 路径上的每个点都停一遍,考虑每次停最多停 $n$ 个市场,那么最终答案的上界就是 $O(n^2)$ 。

根据以上性质,可以发现似乎枚举答案复杂度不高,可以转化为判定性问题。而网络流恰好可以解决判定性问题。所以考虑现在要做的就是如何建一个流图,使得跑出来的最大流就是当前能够运输的最多的人数。

发现决策对时间负责,那么每个时间,一个点可以走出去或者原地傻愣。根据状态最原始的表示方式,可知如果将每个时刻的每个点都单列一个状态,恰好可以转移。

所以建一个超级 $\rm S$ 连向每个 $t$ 的 $0$ ,建一个超级 $\rm T $ 让每个 $t$ 的 $-1$ 连向它,剩下的就按照转移来建就好了。

最后写了个 dinic…还是dinic好…

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

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

const int M = 4010 ;
const int N = 500010 ;
const double eps = 1e-9 ;

int s ;
int ans ;
int cnt ;
int res ;
int n, m ;
int dis[N] ;
int cur[N] ;
int vis[N] ;
int _s, _t ;
int head[N] ;
int extra[N] ;
queue <int> q ;
struct ed{
int to ;
int from ;
int flow ;
int next ;
}e[N * 2] ;

void add(int a, int b, int c){
to(++ cnt) = b ;
fw(cnt) = c ; fr(cnt) = a ;
next(cnt) = head[a] ; head[a] = cnt ;
}
bool bfs(){
for (int i = 0 ; i <= n ; ++ i)
dis[i] = 0, cur[i] = head[i] ; dis[_t] = 0 ;
dis[_s] = 1 ; q.push(_s) ;
while (!q.empty()){
int x = q.front() ; q.pop() ;
for (int k = head[x] ; ~k ; k = next(k))
if (!dis[to(k)] && fw(k) > 0)
dis[to(k)] = dis[x] + 1, q.push(to(k)) ;
}
return (bool)(dis[_t]) ;
}
int dfs(int x, int aim, int f){
int ret = 0, minf ;
if (x == aim || !f) return f ;
for (int &k = cur[x] ; ~k ; k = next(k)){
if (dis[to(k)] != dis[x] + 1) continue ;
if (( minf = dfs(to(k), aim, min(f, fw(k))) ) > 0){
ret += minf, fw(k) -= minf, fw(k ^ 1) += minf ;
f -= minf ; if (f <= 0) break ;
}
}
return ret ;
}
int fa[N] ;
int rn[N] ;
int ctn[N] ;
int ways[M][M] ;

int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]) ;
}
int main(){
int nn, mm ;
_s = 0 ; _t = 50000 ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
cin >> nn >> mm >> s ; n = nn + 2 ;
for (int i = 0 ; i <= n ; ++ i) fa[i] = i ;
for (int i = 1 ; i <= mm ; ++ i){
cin >> rn[i] >> ctn[i] ;
for (int j = 0 ; j < ctn[i] ; ++ j){
cin >> ways[i][j] ; ways[i][j] += 2 ;
if (j > 0) fa[find(ways[i][j])] = find(ways[i][j - 1]) ;
}
}
if (find(2) != find(1))
return puts("0"), 0 ; else nn += 2 ;
for (res = 0 ; ; ++ res){
add(_t, res * nn + 1, 0) ;
add(res * nn + 2, _s, 0) ;
add(res * nn + 1, _t, 100000000) ;
add(_s, res * nn + 2, 100000000) ;
if (res){
for (int i = 1 ; i <= nn ; ++ i){
add(res * nn + i, (res - 1) * nn + i, 0) ;
add((res - 1) * nn + i, res * nn + i, 100000000) ;
}
for (int i = 1 ; i <= mm ; ++ i){
int r = ctn[i] ;
int x = ways[i][res % r] ;
int y = ways[i][(res - 1) % r] ;
x += nn * res, y += nn * (res - 1) ;
add(y, x, rn[i]), add(x, y, 0) ;
}
}
n = 1 + (res + 1) * nn ;
while (bfs()) ans += dfs(_s, _t, 100000000) ;
if (ans >= s) return printf("%d\n", res), 0 ;
}
return 0 ;
}