自动搬运

查看原文

来自洛谷，原作者为

	Lyrella 倒闭了，自闭了|羊角包 & 锦依卫|我也想要金钩惹~

搬运于2025-08-24 22:18:01，当前版本为作者最后更新于2025-06-04 10:06:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

这道题需要你会最小乘积模型，但是此篇题解不会进行非常详细的讲解，不会的话建议去看我的博客了解一下。

题解

首先这道题需要我们求一个割，这是显然的。但是这并不是一个普通的最小割，题目中有两维的限制让我们难以直接处理。面对这种需要最小化两种元素乘积的题目我们能想到最小乘积模型。这里大概讲一下。

首先我们将题目中的花费当成 $x$，影响当成 $y$。我们把每一种不同的割抽象成平面上的一个点 $(x,y)$。现在我们要求 $x\times y$ 的最小值就可以转化成我们在平面上找一个点满足这个点所在的反比例函数的 $k$ 最小。

考虑如何去找目标点，考虑目标点一定在这些割对应的点组成的下凸壳上，这是显然的。于是我们的思路就是将下凸壳上的点计算并更新答案。

考虑我们怎么去找下凸壳上的点？首先我们能够找到两个点，分别是只满足 $x$ 最小的点 $A$ 和只满足 $y$ 最小的点 $B$。这两个点一个的横坐标最小，另一个纵坐标最小。我们从这两个点入手。

我们有了两个点 $A,B$，考虑在直线 $AB$ 下方找一个点 $C$ 使得 $S_{\triangle ABC}$ 最大，这个点 $C$ 显然一定在下凸壳上。我们计算 $C$ 处的答案然后递归到两边更新答案即可。

现在我们的目标是找到点 $C$。考虑找一个点 $C$ 使得 $S_{\triangle ABC}$ 最大，也就是 $\overrightarrow{AB}\times\overrightarrow{AC}$ 最小（因为其值为负），所以我们现在暴力拆掉叉积，有：

$$\begin{aligned} \overrightarrow{AB}\times\overrightarrow{AC}&=(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A)\\ &=(y_A-y_B)x_C+(x_B-x_A)y_C-x_By_A+y_Bx_A \end{aligned} $$

因为后面两项都是定值所以我们需要找前两项的最小值，于是我们在求最小割的时候把流量设为 $(y_A-y_B)w_i+(x_B-x_A)e_i$ 即可。

于是这道题就这么水灵灵地过啦，时间复杂度是网络流的复杂度乘上下凸壳上点的数量。具体复杂度笔者不是很会证，个人感觉玄学，反正是 $O(\text{能过})$ 就对了。

代码

写的时候就是一个网络流板子加上分治下凸壳的函数。注意每次跑网络流前清空一些数组。代码细节较少，故不放代码。