你说得对，但是我认为这是 implemention

NATO · 2025-02-17 14:14:28 · 题解

提供一种纯并查集的做法。

思路浅析：

考虑我们走到一个点 (i,j) 上，我们没有超过它的限制 d_{i,j}，但是我们可能因为其它点限制更小就走不出去了，所以这个限制不够严，考虑求出 d'_{i,j} 表示我走到这个点上，在能够走出去的条件下最多能够持有的金币数量。

怎么搞出来这个东西呢？容易想到可以值域扫描线+并查集。

具体地，我们做一个从大到小的值域扫描线，保留所有 d\ge x 的点，扫到大小 x 时就把所有 d=x 的点和四周的 d\ge x 的点合并，一个未碰到边缘的连通块和碰到边缘的连通块合并的时候就是未碰到边缘的连通块内那些点的 d'。

现在，我们就去掉了走回来这个过程。

考虑如何求出答案。考虑求出 dp_{i,j} 表示走到 (i,j) 可以获得的金币数量。

考虑一个和上面恰好相反的从小到大的扫描线，保留所有 d'\ge x 的点，不过现在我们就不需要考虑走出去了。我们每次求出 d'=x 的 dp_{i,j}。

发现如果在 d'=x 时有一个 dp_{i,j}，我们就需要给它所在的连通块的每个位置的 dp 值和它取 \max。

转换一下，我们记录整个连通块的 dp 值即可。

转移是容易的，d'=x 时 dp_u=\min(x,dp_u+sum_{u,x})，其中 sum_{u,x} 表示以 u 为代表的联通块内 d'=x 的点数。

然后随着 x 的增大，联通块会发生分裂，分裂这个过程可以通过做一次从大到小的扫描线变成合并，记录一下怎么合并的即可实现分裂。

考虑分裂出了两个分别以 u,v 为代表的联通块（u 为原来连通块的代表点），在此之前对于这两个连通块我可以拿了 u 中 d'>x（\le x 的已经考虑过了）位置的金币再走到 v，反之亦然，但是我不能拿超过 x 个金币，不然我就走不了了。

于是有转移：