ABC397G 题解

显然能够二分。

check 答案是否 $\ge 1$ 显然不弱于最小割，所以本题明显需要使用网络流。

我们不妨直接钦定 $1$ 到所有点的单源最短路。

具体地，我们使用一个常用的建图技巧，并求其最小割：对于一个点 $d_{i,j}$，其与 $S$ 连通等价于 $\text{dis}_i \ge j$，通过建立 $(d_{i,p},d_{i,p+1},1)$ 来强制必须断且仅断一条 $i$ 链上的点（特别地，需要连接 $(S,d_{i,0},+\infty)$）。

在此基础上，我们可以添加一些限制，形如“如果 $\text{dis}_i \ge p$，那么 $\text{dis}_j \ge q$”。 其建边形式为 $(d_{i,p},d_{j,q},+\infty)$。如果 $\text{dis}_i \le p$ 并且 $\text{dis}_j > q$，那么 $d_{i,p}$ 与 $S$ 连通，$d_{j,q}$ 与 $T$ 连通，不符合是一个割的定义。你也可以使用边权的代价来废除本限制。

在本题中，如果存在一条边 $(u,v)$，那么显然有 $\text{dis}_v \le \text{dis}_u +1$。也就是说对于每一个 $p$，有如果 $p \le \text{dis}_v$，那么 $p \le \text{dis}_v \le \text{dis}_u+1$，即 $p-1 \le dis_u$。所以可以建立 $(d_{v,p},d_{u,p-1},+\infty)$。

当 $(u,v)$ 边权明确为 $0$ 时，就有 $\text{dis}_v \le \text{dis}_u$。如果 $p \le \text{dis}_v$，那么 $p \le \text{dis}_u$。所以可以建立从 $d_{v,p}$ 到 $d_{u,p}$ 的边。但是你可以花费 $1$ 的代价来撤销本限制，所以边权为 $1$，即需要建立 $(d_{v,p},d_{u,p},1)$ 的边。显然对于同一条 $(u,v)$，一种赋权方案中其引出的边最多只会违反一个，所以最优解中这类边只会割去一个。

一个补丁就是你必须让 $\text{dis}_1 =0,\text{dis}_n=mid$。直接固定割掉 $(d_{1,0},d_{1,1})$ 以及 $(d_{n,mid},T)$ 即可。

在一次判定中，我们只需要看割是否 $\le K+n-2$（$n-2$ 是为除 $1,n$ 之外每一个点选择一个最短路的固定开销），而一共建立了 $nm$ 条边，所以增广一次就是 $O(nm)$ 的。所以一次判定就是 $Knm$ 的。总时间复杂度为 $O(Knm \log n)$。