题解：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$ 最小的。

$n\leq 200,m\leq 500, K\leq 5$。

考虑 $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)$，实际上相当快。