拆点

拆点是一种图论建模思想，常用于

网络流，用来处理 点权或者点的流量限制 的问题，也常用于 分层图。

结点有流量限制的最大流

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

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

如果原图是这样：

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

分层图最短路

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

其中， 表示 的父亲节点， 表示当前所走的边的边权。当 时，=。

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