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)。