70.拆点

拆点

拆点不是一种具体算法，而是一种图论中的重要思想，样用于网络流，用来处理点权或者点的流量限制问题，也适用于分层图

把一个节点 $u$ 拆成两个节点 $u, u^{'}$ 然后 $u$ 承载别的连到这个点的边， $u^{'}$ 往别的节点练边

原图是这样的

拆点后是这样的

看一个例题

洛谷 P4568「JLOI2011」飞行路线

有 $k$ 次零代价通过一条路径，求总的最小花费

我们可以采用 DP 思想，定义 $d i s [i] [j]$ 表示从起点到 $i$ ，使用看 $j$ 次免费通行权限后的最短路径，显然转移方程为

d i s [i] [j] = min {min {d i s [f r o m] [j - 1]}, min {d i s [f r o m] [j] + w}}

其中 $f r o m$ 为 $i$ 的父节点， $w$ 为这条路的边权，当 $j - 1 \leq k$ 时， $d i s [f r o m] [j] = I N F$

实际上，这个 DP 就相当于把每个节点拆成了 $k + 1$ 个节点，然后在分层图上跑最短路