【网络流24题专题】6 · 有趣的费用流

24题中比较新颖有趣的费用流题目:

分别是 loj#6014 最长可重区间集、loj#6227 最长可重线段集问题 和 loj#6008 餐巾计划。

啊,24道题里面,1道假题,还有两道状压bfs,因为与网络流无瓜就忽略了。

总之呢,总算是做完了啊。

最长 k 可重区间集

给定实直线 $ L $ 上 $ n $ 个开区间组成的集合 $ I $,和一个正整数 $ k $,试设计一个算法,从开区间集合 $ I $ 中选取出开区间集合 $ S \subseteq I $,使得在实直线 $ L $ 的任何一点 $ x $,$ S $ 中包含点 $ x $ 的开区间个数不超过 $ k $。且 $ \sum\limits_{z \in S} | z | $ 达到最大。这样的集合 $ S $ 称为开区间集合 $ I $ 的最长 $ k $ 可重区间集。$ \sum\limits_{z \in S} | z | $ 称为最长 $ k $ 可重区间集的长度。

对于给定的开区间集合 $ I $ 和整数 $ k $,计算开区间集合 $ I $ 的最长 $ k $ 可重区间集的长度。

$ 1 \leq n \leq 500, 1 \leq k \leq 3 $

首先一拿出来,这不就是匹配问题嘛?一个点最多匹配 $k$ 个区间。于是每个位置建一个点,然后连向覆盖自己的点,然后…好像不太对?其一他没给下标的取值范围,其二一个线段覆盖多个点,要么都覆盖要么都不覆盖,这个限制很难表示…

于是好像不知道从何处入手了。发现一个这样的性质,就是永远不会选择 $k$ 个以上交于 $1$ 点的区间。也就是说,如果两个区间彼此之间没有交,就可以同时选;否则能不能同时选,看情况。这像极了「限制」,也就是如果两个区间之间没有交,那两者不存在限制;否则存在 $k$ 的限制。

根据一开始的匹配,可以猜到大致上用网络流是可行的。并且似乎网络流很适合用流量来表征限制。那么考虑,如果两个区间不存在限制,那么应该怎么办——网络流类似电流,所以此时如果串联的话,就代表着可以同时选;那么如果存在限制,就意味着不能串联。根据这一点,考虑如何串联。发现本质上是将两个不交的区间中间连 $f=\infty,c=0$ 的边。

这一点就引申出两个建图方法,其本质是相同的:

1、建立一个超级源 $\rm S$ 和一个源 $\rm S’$ ,中间连 $f=k,c=0$ 的边,目的是提供初始流量。$\rm S’$ 向每个区间的左端点连一条 $f=1,c=-1$ 边。然后区间左端点向右端点连边 $f=1,c=-len$ 表示贡献,每个右端点再向 $\rm T $ 连边即可。如果两个区间不交,就由一个区间的 $r$ 连向另一个区间的 $l$ (当然要按秩啦)。思考这样做的合理性,对于相交的区间,一定是并联;否则的话就是串联(其实叫做混连,但是问题不大)。

2、建立一个源 $\rm S$ 连向数轴上的 $0$ 位置,$f=k,c=0$。然后数轴上每个 $i>0$ 向 $i+1$ 连边 $f=k,c=0$。最后 $maxright$ 向 $\rm T$ 连边。对于一个区间,连法跟1相同。

注意:

1、为什么要拆点?此处拆点的作用值得注意。对于一个区间,本质上应该抽象成一个点。但是在流图里是不存在「点权」这个概念的。所以需要把点权转边权,拆点的作用便在于此。

2、其实上面两个方法,可以通过初中物理里面什么「判断两个电路图是否等价」的知识来解决的233

3、由于本题保证了「开区间」,所以可以直接 $l\to r,len=r-l$ 。当然如果是闭区间,只需要改成 $l\to r+1$ 即可。

4、上面的第二个方案,发现最终可能存在很多数轴上的点 $i$ 只与 $i-1,i+1$ 连了 $f=k,c=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
const int N = 200010 ;
const int I = 998244353 ;

#define ft first
#define sc second
#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
#define pint pair<int, int>

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 len[N] ;
pint base[N] ;
int _n, _k, tot ;
map <int, int> Id, buc ;
map <int, int> :: iterator t ;

int main(){
int u, v, f, c ;
cin >> _n >> _k ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= _n ; ++ i){
cin >> base[i].ft >> base[i].sc ;
len[i] = base[i].sc - base[i].ft ;
}
for (int i = 1 ; i <= _n ; ++ i){
if (!Id.count(base[i].ft)) buc[base[i].ft] ++ ;
if (!Id.count(base[i].sc)) buc[base[i].sc] ++ ;
}
add(0, 1, _k, 0) ; add(1, 0, 0, 0) ;
for (t = buc.begin() ; t != buc.end() ; ++ t)
Id[t->ft] = ++ tot ; _s = 0 ; _t = tot + 1 ;
for (int i = 1 ; i <= tot ; ++ i)
add(i, i + 1, I, 0), add(i + 1, i, 0, 0) ;
for (int i = 1 ; i <= _n ; ++ i){
//cout << Id[base[i].ft] << " " << Id[base[i].sc] << endl ;
add(Id[base[i].ft], Id[base[i].sc], 1, -len[i]) ;
add(Id[base[i].sc], Id[base[i].ft], 0, len[i]) ;
}
n = _t + 1 ; ek() ;
cout << -ans << endl ;
}

最长 k 可重线段集问题

给定平面 $\text{x-o-y}$上 $n$ 个开线段组成的集合 $\text{I}$,和一个正整数 $\rm k$ 从开线段集合 $\text{I}$ 中选取出开线段集合 $\text{S}\in \text{I}$, 使得在 x 轴上的任何一点 $\text{p}$ , $\text{S}$ 中与直线 $\text{x}=\text{p}$ 相交的开线段个数不超过 $\text{k}$ ,且 $\sum_{\text{z} \in \text{S}}|z|$ 达到最大。这样的集合 $\text{S}$ 称为开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。

对于任何开线段 $\text{z}$,设其端点坐标为 $( x_0 , y_0 )$ 和 $( x_1 , y_1 )$,则开线段 $\text{z}$ 的长度 $|\text{z}|$ 定义为: $|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$。对于给定的开线段集合 $\text{I}$ 和正整数 $\text{k}$ ,计算开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。

$1\leq n\leq500,$ $1 \leq k \leq 13$.

发现和「区间集」那题没啥区别,只用关心 $x$ 轴,换一下长度的求法…好像有点不对?因为如果存在两条线段均垂直于 $x$ 轴,且两条线的左右端点分别都是 $x_i$ ,这样的话,建出图来这俩线段是串在一起不交的,但是本质上应该交。

于是自然想到,要换种表示方法在 $x$ 轴上表示一个线段。那么如果是在数轴上,比较简单的方式就是扩域。每个线段 $i$ 的左右端点 $(l_i,r_i)$ 变换成 $(2\times l_i,2\times r_i)$——听上去很不错,这样的话就相当于每个下标多了一个空间。那么对于一个左右端点相同的区间 $(x,x)$ ,就可以连边成 $(2\cdot x,2\cdot x + 1)$。这样的话,原本左右端点不用的区间也要改——由于那些相同的区间右端点加了 $1$,所以如果存在这样两个线段 $(p,p)$ 、 $(p,q)$ ,那么原本不交的两个区间,在扩域之后变成了相交的 $(2p,2p+1)$、$(2p,2q)$ 。

处理方式很简单,对于一个 $p\not=q$ 的区间 $(p,q)$,连边 $(2p+1,2q)$ 即可。思考这么做为啥是对的。对于原本存在的两个均不垂直 $x$ 轴的线段,他们如果相交,那么交的那一端,$r_1-l_2\geq 1$ ;如果不交,那么有 $l_2-r_1\geq 1$ 。扩域之后就变成了 $\geq 2$ 。所以如果只是左端点增加 $1$ ,根本不影响判定。

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
int len[N] ;
pint base[N] ;
int _n, _k, tot ;
map <int, int> Id, buc ;
map <int, int> :: iterator t ;

int calc(int a, int b, int c, int d){
return (int)sqrt((ll)(a - c) * (a - c) + (ll)(b - d) * (b - d)) ;
}
int main(){
int a, b, c, d ;
cin >> _n >> _k ; cnt = -1 ;
memset(head, -1, sizeof(head)) ;
for (int i = 1 ; i <= _n ; ++ i){
cin >> a >> b >> c >> d ;
len[i] = calc(a, b, c, d) ;
base[i].ft = a << 1 ;
base[i].sc = c << 1 ;
if (a == c)
++ base[i].sc ;
else ++ base[i].ft ;
}
for (int i = 1 ; i <= _n ; ++ i){
if (!Id.count(base[i].ft)) buc[base[i].ft] ++ ;
if (!Id.count(base[i].sc)) buc[base[i].sc] ++ ;
}
add(0, 1, _k, 0) ; add(1, 0, 0, 0) ;
for (t = buc.begin() ; t != buc.end() ; ++ t)
Id[t -> ft] = ++ tot ; _s = 0 ; _t = tot + 1 ;
for (int i = 1 ; i <= tot ; ++ i)
add(i, i + 1, I, 0), add(i + 1, i, 0, 0) ;
for (int i = 1 ; i <= _n ; ++ i){
//cout << Id[base[i].ft] << " " << Id[base[i].sc] << endl ;
add(Id[base[i].ft], Id[base[i].sc], 1, -len[i]) ;
add(Id[base[i].sc], Id[base[i].ft], 0, len[i]) ;
}
n = _t + 1 ; ek() ;
cout << -ans << endl ;
}

餐巾计划

一个餐厅在相继的 $ n $ 天里,每天需用的餐巾数不尽相同。假设第 $ i $ 天需要 $ r_i $ 块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 $ P $ 分;或者把旧餐巾送到快洗部,洗一块需 $ M $ 天,其费用为 $ F $ 分;或者送到慢洗部,洗一块需 $ N $ 天,其费用为 $ S $ 分($ S < F $)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $ n $ 天中餐巾使用计划,使总的花费最小。

$ 1 \leq n \leq 1000 $

一道有趣的题。

嗯,本来想整理一下自己错的那几版是怎么错的,然后发现我忘了…

然后最近错的一版我是这么建的边:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(){
cin >> N ;
int p, m, f, n, s ;
S = 0, T = N << 1 | 1 ;
memset(head, -1, sizeof(head)) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
scanf("%d%d%d%d%d", &p, &m, &f, &n, &s) ;
for (i = 1 ; i <= N ; ++ i)
Add(S, i, Inf, 0), Add(i + N, T, base[i], 0) ;
for(i = 1 ; i < N ; ++ i) Add(i, i + 1, Inf, 0) ;
for (i = 1 ; i <= N ; ++ i){
Add(i, i + N, base[i], p) ;
//Add(S, i + N, base[i], p) ;
if (i + m <= N) Add(i, i + m + N, base[i], f) ;
if (i + n <= N) Add(i, i + n + N, base[i], s) ;
}
MCMF() ; cout << Ans << endl ;
}

那么实质上这个题应该怎么做呢?zay鸽鸽教育我:

大概就是 $\rm S$ 到晚上的边实际上是当天餐巾用完之后要提供 $r_i$ 块脏的餐巾——这个思路,是逆常识的,单纯是为了让每个点到 $T$ 的边满流才这么做。

于是最后就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
cin >> N ;
int p, m, f, n, s ;
S = 0, T = N << 1 | 1 ;
memset(head, -1, sizeof(head)) ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
scanf("%d%d%d%d%d", &p, &m, &f, &n, &s) ;
for (i = 1 ; i <= N ; ++ i)
Add(S, i + N, base[i], 0), Add(i, T, base[i], 0) ;
for(i = 1 ; i < N ; ++ i) Add(i, i + 1, Inf, 0) ;
for(i = 1 ; i < N ; ++ i) Add(i + N, i + N + 1, Inf, 0) ;
for (i = 1 ; i <= N ; ++ i){
//Add(i, i + N, base[i], p) ;
Add(S, i, base[i], p) ;
if (i + m <= N) Add(i + N, i + m, Inf, f) ;
if (i + n <= N) Add(i + N, i + n, Inf, s) ;
}
MCMF() ; cout << Ans << 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
#include <queue> 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define MAXN 1005000
#define to(k) E[k].to
#define Inf 1000000007

using namespace std ;
struct Edge{
int to, next, f, c ;
}E[MAXN] ;int head[MAXN], cnt = -1, x ;
int Ans, S, T, N, base[MAXN], i, j, k, dist[MAXN], F[MAXN] ;
struct state{
int dist, num ;
bool operator <(const state & now) const{ return dist > now.dist ; }
} ; priority_queue <state> q ; bool vis[MAXN] ; int H[MAXN], Pre[MAXN], Last[MAXN] ;

inline bool dijks(){
for (i = 0 ; i <= T ; ++ i)
dist[i] = F[i] = Inf, vis[i] = 0 ;
dist[S] = 0 ; q.push((state){dist[S], S}) ;
while (!q.empty()){
state now = q.top() ; q.pop() ;
int num = now.num, dis = now.dist ;
if (vis[num]) continue ; vis[num] = 1 ;
for (k = head[num] ; k != -1 ; k = E[k].next){
int qwq = dis + H[num] - H[to(k)] + E[k].c ;
if (qwq < dist[to(k)] && !vis[to(k)] && E[k].f){
dist[to(k)] = qwq, F[to(k)] = min(F[num], E[k].f),
q.push((state){dist[to(k)], to(k)}), Pre[to(k)] = num, Last[to(k)] = k ;
}
}
}
return dist[T] < Inf ;
}
inline void Add(int u, int v, int f, int c){
E[++ cnt].to = v, E[cnt].c = c ;
E[cnt].f = f, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].c = -c ;
E[cnt].f = 0, E[cnt].next = head[v], head[v] = cnt ;
}
inline void MCMF(){
Ans = 0 ;
while (dijks()){
int Ed = T ; Ans += (dist[T] - H[S] + H[T]) * F[T] ;
while (Ed) 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 << dist[T] << endl ; */
}
}

int main(){
int p, m, f, n, s ; cin >> N ; memset(head, -1, sizeof(head)) ; S = 0, T = N << 1 | 1 ;
for (scanf("%d%d%d%d%d", &p, &m, &f, &n, &s), i = 1 ; i <= N ; ++ i) scanf("%d", &base[i]) ;
// for (scanf("%d%d%d%d%d", &p, &m, &f, &n, &s), i = 1 ; i <= N ; ++ i) Add(S, i, base[i], 0), Add(i + N, T, base[i], 0) ;
for (i = 1 ; i <= N ; ++ i) Add(S, i, base[i], 0), Add(i + N, T, base[i], 0) ; for(i = 1 ; i < N ; ++ i) Add(i, i + 1, Inf, 0) ;
for (i = 1 ; i <= N ; ++ i) {Add(S, i + N, Inf, p), Add(i, i + N, Inf, p) ; if (i + m <= N) Add(i, i + m + N, Inf, f) ; if (i + n <= N) Add(i, i + n + N, Inf, s) ;}
/*for (i = 1 ; i < N ; ++ i) Add(i, i + 1, Inf, 0) ; //1
for (i = 1 ; i <= N ; ++ i) {Add(S, i + N, Inf, p), Add(i, i + N, base[i], p) ; if (i + m <= N) Add(i, i + m + N, Inf, f) ; if (i + n <= N) Add(i, i + n + N, Inf, s) ;}
*/MCMF() ; cout << Ans << endl ;
}