题解：P15246 [WC2026] 猫和老鼠

· · 题解

题意

数轴 [0,m] 上有一只老鼠，初始时可能位于数轴上的任意点。这只老鼠可以在数轴上任意移动，但是任何时刻瞬时速度不超过 1 个单位每秒。

有 n 只机器猫，部署第 i 只的代价为 w_i，部署后它会在 t_i 时刻出现在 a_i，以每秒 1 个单位的速度向 b_i 移动。

老鼠初始时有 k 点血量，如果在某个时刻和一只机器猫完全重合，就会减 1 点血量，这只机器猫也会被销毁。

求最小代价，使得无论老鼠如何移动，最终血量都 \leq 0。多测，\sum n\leq 3\times 10^5，k\leq 10。

题解

场外选手。激战一百年，也是自己做出来了，有点开心。

考察老鼠的移动有什么限制，移速不超过 1，意味着对于每一个时间段都有 |\Delta x|\leq \Delta t\Leftrightarrow -\Delta t\leq \Delta x\leq \Delta t，也就是说，\Delta t+\Delta x\geq 0\land \Delta t-\Delta x\geq 0。考虑变换坐标，令 (t,x)\gets (t-x,t+x)，这样老鼠的初始位置为 (-p,p)，且任意时刻都要满足 \Delta x,\Delta y\geq 0，相当于只能朝着右上方移动。考察 0\leq x\leq m 的限制，代入 x=\dfrac{(t+x)-(t-x)}{2}，可以得出 t-x\leq t+x\land t-x\geq t+x-2m，也就是说，老鼠还被限制在 y=x 和 y=x+2m 两条直线之间。

考虑变换坐标后，机器猫的移动路径。若 a_i\leq b_i，则

\begin{align*} x=a_i+t-t_i&\Leftrightarrow t-x=t_i-a_i\\ t\in [t_i,t_i+(b_i-a_i)]\land x\in [a_i,b_i]&\Leftrightarrow t+x\in [t_i+a_i,t_i+(b_i-a_i)+b_i] \end{align*}

此时机器猫的移动路径为一条垂直线段。

同理，若 a_i>b_i，可以得到 t+x=t_i+a_i\land t-x\in [t_i-a_i,t_i+(a_i-b_i)-b_i]，机器猫的移动路径为一条水平线段。

现在问题就转化成了：有一个点 (-p,p)，只能朝着右上方移动，被限制在 y=x 和 y=x+2m 两条直线之间。现在有一些垂直或水平的线段，要求以最小代价选取一些线段，使得无论点如何移动，都会碰到至少 k 条线段。

不妨先做 k=1，相当于要选出若干条线段使得老鼠无法通过。考察一组合法线段的形态：

黑色实线是我们选出来的线段。可以发现，选出来的线段一定能围出一个分界线（图中绿色虚线），使得一边是老鼠可达的区域，另一边是老鼠不可达的区域。不妨给分界线定向，以与 y=x 的交点为起点，与 y=x+2m 的交点为终点。可以发现这样定向之后，沿着分界线走，向左或向上走时一定是沿着线段走的，向右或向下走时则不是（这是老鼠只能往右上走的限制自然形成的分界线）。不妨考察相邻线段之间的限制，钦定一条线段的起点为靠近 y=x 的那一端，终点为另一端，设 u 为第 i 条线段的终点，v 为第 i+1 条线段的起点，则可以分讨得出，u 和 v 之间的限制为 u_x\leq v_x\land u_y\geq v_y。

据此考虑图论建模，套路地将线段 i 拆成 in_i,out_i 两个点，从 in_i 向 out_i 连一条权值为 w_i 的边。对于任意两条线段 i,j，若 i 的终点 u 和 j 的起点 v 满足前文中的性质，则从 out_i 向 in_j 连一条权值为 0 的边。最后建立源点 S 和汇点 T，对于每条线段 i，若 i 的起点在 y=x 上，则从 S 向 in_i 连一条权值为 0 的边；若 i 的终点在 y=x+2m 上，则从 out_i 向 T 连一条权值为 0 的边。这样建图后，不难看出答案就是 S 到 T 的最短路。

考虑进一步推广到 k>1 的情况，此时我们需要选出 k 条不交的分界线。不难想到网络流，将连边改为：

此时从 S 到 T 的 1 个单位的流量就代表选出了一条分界线，那么我们限制最大流 \leq k，求最小费用最大流即可。具体来说，每一轮增广的流量为 1，那么我们增广 k 轮即可，最终费用就是答案，若无法增广 k 轮则无解。

建出来的图边数是 \mathcal{O}(n^2) 的，时间复杂度为 \mathcal{O}(kn^3)，可以获得 56 分。

进一步优化，注意到连边条件为二维偏序的形式，因此考虑 CDQ 分治优化建图。具体来说，考虑 n 条线段的 2n 个端点，将所有端点按 x 坐标从小到大排序，x 坐标相同的按 y 坐标从大到小排，y 坐标相同的把线段终点排在起点前面（读者需要理解一下这个排序方式，其实是为了处理取等）。CDQ 分治，递归到 [l,r] 时处理所有跨过 mid 的连边：分别取出左侧的线段终点和右侧的线段起点，按 y 坐标排序，枚举左侧的线段终点 u，则其能连向的线段起点 v 是一段前缀，使用前缀优化建图即可。这样点数和边数都是 \mathcal{O}(n\log{n}) 级别的，时间复杂度为 \mathcal{O}(kn^2\log^2{n})，可以获得 84 分。

改成用原始对偶求费用流，由于边权非负，初始时不必跑 SPFA，将势能初始化为 0 即可，时间复杂度为 \mathcal{O}(kn\log^2{n})，可以获得 100 分。