跳转至

拆点

拆点是一种网络流建模思想,用来处理点权或者点的流量限制的问题。这种思路同样可以用于其他的图论算法中(比较经典的有分层图

例题 经典问题 结点有流量限制的最大流

如果把结点转化成边,那么这个问题就可以套板子解决了。

我们考虑把有流量限制的结点转化成这样一种形式:由两个结点 u,v和一条边 <u,v>组成的部分。其中,结点 u承接所有从原图上其他点的出发到原图上该点的边,结点 v引出所有从原图上该点出发到达原图上其他点的边。边 <u,v>的流量限制为原图该点的流量限制,再套板子就可以解决本题。这就是拆点的基本思想。

如果原图是这样:

拆点之后的图是这个样子:

例题luogu P4568[JLOI2011]飞行路线

题目大意:有 n个结点, m条边, k张旅行券,可以使用一张旅行券使得经过该边的边权除以二向下取整,求从结点 st的最短路的长度。

当然可以使用 DP 方法解决这道题。我们考虑使用拆点的解法。

将每个结点拆成 k个点,这样图就可以形象化地看做是 k层,每层的结点之间连上原来就有的边,边权和原来相等;若图上存在边 <u,v>,则在当前层的 u所对应的结点和更高一层的 v所对应的结点,连接一条边权为原边权除以二向下取整的边。这样可以保证最多只使用 k次旅行券,因为每次从较低的一层到上面一层,就相当于是使用了一张旅行券。以最底层的 s所对应的点跑单元最短路即可。


评论