拆点
拆点是一种 网络流 建模思想，用来处理 点权或者点的流量限制 的问题。这种思路同样可以用于其他的图论算法中（比较经典的有 分层图 ）
例题 经典问题 结点有流量限制的最大流¶
如果把结点转化成边，那么这个问题就可以套板子解决了。
我们考虑把有流量限制的结点转化成这样一种形式：由两个结点 和一条边 组成的部分。其中，结点 承接所有从原图上其他点的出发到原图上该点的边，结点 引出所有从原图上该点出发到达原图上其他点的边。边 的流量限制为原图该点的流量限制，再套板子就可以解决本题。这就是拆点的基本思想。
如果原图是这样：
拆点之后的图是这个样子：
例题luogu P4568[JLOI2011]飞行路线¶
题目大意：有 个结点， 条边， 张旅行券，可以使用一张旅行券使得经过该边的边权除以二向下取整，求从结点 到 的最短路的长度。
当然可以使用 DP 方法解决这道题。我们考虑使用拆点的解法。
将每个结点拆成 个点，这样图就可以形象化地看做是 层，每层的结点之间连上原来就有的边，边权和原来相等；若图上存在边 ，则在当前层的 所对应的结点和更高一层的 所对应的结点，连接一条边权为原边权除以二向下取整的边。这样可以保证最多只使用 次旅行券，因为每次从较低的一层到上面一层，就相当于是使用了一张旅行券。以最底层的 所对应的点跑单源最短路即可。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用