题解：qoj#1359 Setting Maps

· · 个人记录

题意简述

给定 n 个点，m 条边的简单有向图，每个点有点权 c_i，并给出上面的两个点 s,t(s\neq t) 和一个正整数 K。

要求构造一个点集 S，满足从 s 到 t 的任意一条路径中，至少有 K 个点在 S 中，且 S 是所有这样的点集中 \sum_{u\in S}c_u 最小的。

## 解法 考虑 $K$ 等于 $1$ 的情况，这是一个最小割点集问题，拆点转为割边后求最小割即可。 对于 $K$ 更大的情况，考虑类似建图。 现在一条路径要被“割 $K$ 次”，那么将图复制 $K$ 层，点 $x$ 第 $i$ 层入点记为 $x_i^+$，出点记为 $x_i^-$。 对于每个 $x$，连边 $(x_i^+,x_i^-,c_x),(x_i^+,x_{i+1}^-,+\infin)$。对于每条原图上的边 $(x,y)$，连边 $(x_i^-,y_i^+,+\infin)$。如果某个 $(x_i^+,x_i^-,c_x)$ 在最小割中，则 $x$ 选入点集 $S$ 中。这样可以发现，对于任意一条原图上 $s$ 到 $t$ 的路径，如果在 $S$ 中的点少于 $K$ 个，必然存在一条从 $s_1^+$ 到 $t_K^-$ 的路径。 这个建图的问题是，一个点 $x$ 如果被选入点集，理应同时割去所有 $(x_i^+,x_i^-)$，只需要 $c_x$ 的代价，而不是当作 $K$ 条边选入最小割，也就是需要说明在最小割中每个 $x$ 只存在一个 $(x_i^+,x_i^-)$ 被割去。 对于固定的点集 $S$，设 $f_x$ 为 $s$ 到 $x$ 的所有路径上（不包括 $x$）最少有多少个点在 $S$ 中，$g_x$ 为 $x$ 到 $t$ 的所有路径上（不包括 $x$）最少有多少个点在 $S$ 中。那么对于 $x\in S$，要求 $f_x+g_x+1\geq K$。也就是说，只需要考虑 $s$ 到 $x$ 且上面恰有 $f_x$ 个点在 $S$ 中（不包括 $x$）的路径（因为对于其他路径，即使当作 $x\notin S$ 也满足要求），那么对应到上面的最小割中，只需要割去 $(x_{f_x}^+,x_{f_x}^-)$ 这一条边即可。 使用 Dinic 算法求最大流，总复杂度 $O((nk)^2m)$，实际上相当快。