想到了费用流,但是没有想到可以这样处理绝对值……
Part1. 题意
(中文题面是 wzy yy 的)
一个平面直角坐标系上有 $n$ 堆山楂和 $n$ 堆柠檬,第 $i$ 堆山楂有 $t_i$ 个,放在坐标 $(x_i,y_i)$,第 $i$ 堆柠檬有 $t_i’$ 个,放在坐标 $(x_i’,y_i’)$。
这 $n$ 堆柠檬的总数和 $n$ 堆山楂的总数相等,即 $\sum_{i=1}^nt_i=\sum_{i=1}^nt_i’$。
你现在要进行下述操作:
分别选择一堆柠檬和一堆山楂,从中分别拿出 一个 柠檬和山楂;获得的酸度值是这两堆东西的曼哈顿距离。(当一堆东西被拿完后,那一堆就消失了)
显然你可以在若干次操作后拿完所有山楂和柠檬。那么,你最酸可以达到多少?(酸度值的最大值)
Hint. $1\le n\le1000$,$1\le t_i,t_i’\le10$,$0\le x_i,y_i,x_i’,y_i’\le10^9$;
Part2. 考场思路
一来就看到这是个二分图……
最初想的是一个 完全匹配,但是发现这个是边权而非点权,匈牙利算法肯定跑不了(而且时间也会爆炸)。
然后就想到网络流也可以解决匹配问题,又带边权,自然想到这可以跑 最大费用流!感觉没有什么问题,接下来就开始想建图了。
感觉对绝对值这个东西非常的熟悉,但是到计算一堆绝对值的最大值的时候就有一点懵……最后只有暴力建 $n^2$ 条边,也就是每堆山楂和每堆柠檬连边。
当然会 TLE 了。
Part3. 正解
其实我在考场上没有考虑到绝对值的一个非常明显的性质:
$|x|=\max\{x,-x\}$
非常明显,无须证明~
至于这个性质怎么用,后面自然就知道了 : )
如果我们选择 $(a,b)$ 位置上的山楂和 $(c,d)$ 位置上的柠檬,我们可以得到的酸度值是:
然后这意味着什么?
接下来就非常有意思了,我们不是要跑最大费用流嘛,如果我们把第 $i$ 堆山楂和第 $j$ 堆山楂之间连上 $4$ 条边:
那么跑最大费用流时肯定会流到最大的那一条,根据我们之前所说的性质,就是 $|x_i-x_j’|+|y_i-y_j’|$。
但是这样有什么用?连了 $4n^2$ 条边,比原来还连的多了!但是这 $4$ 个式子可以拆成分别只与 $\boldsymbol{i,j}$ 相关的两部分 ——
新建四个点 $a,b,c,d$,每堆山楂向 $a$ 连费用为 $x_i+y_i$ 的边、向 $b$ 连费用为 $x_i-y_i$ 的边、向 $c$ 连费用为 $-x_i+y_i$ 的边、向 $d$ 连 $-x_i-y_i$ 的边 …… 每堆柠檬同理。
那么只要流过点 $a$ ,费用就一定会构成式子:$x_i-x_j’+y_i-y_j’$……流过 $b,c,d$ 同理,分别对应四个式子。
所以边数就能减少到 $4n$ ,就可以过了~
Part4. 源代码
1 | /*Unlucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问~(你们说我是不是下次可以不写这个了……反正肯定没人会问)