网络流常用小技巧拆点

拆点是一种图论建模思想，常用于网络流，用来处理点权或者点的流量限制的问题，也常用于分层图。

一、什么是拆点？

什么是拆点？拆点就是将一个点拆成入点和出点两个点，并在两个点之间建一条边。

为什么要拆点？拆点是为了实现对点的限制。

什么时候需要拆点？当题目中明确说明对点有限制或在实际应用中对点有限制时，我们就需要拆点。例如我们要保证经过某点中转的流量不能大于5（对点有流量限制），那么我们就需要将该点拆成入点和出点，并在两点间建一条容量为5的边，就实现了对点的限制。

做题时一定要看清，如果是对边有限制，就通过流量或流网络来实现；如果是对点有限制，就通过拆点来实现。

二、结点有流量限制的最大流

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

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

如果原图是这样：

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

三、分层图最短路

分层图最短路，如：有 k 次零代价通过一条路径，求总的最小花费。对于这种题目，我们可以采用 DP 相关的思想，设  表示当前从起点 i 号结点，使用了 j 次免费通行权限后的最短路径。显然，dis数组可以这么转移：

其中，from表示 i 的父亲节点，w 表示当前所走的边的边权。当 j-1≥k 时，。

事实上，这个 DP 就相当于把每个结点拆分成了 k+1 个结点，每个新结点代表使用不同多次免费通行后到达的原图结点。换句话说，就是每个结点 ui 表示使用 i 次免费通行权限后到达 u 结点。