本地源文件：docs/graph__node.md

拆点

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

结点有流量限制的最大流

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

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

如果原图是这样：

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

分层图最短路

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

dis𝑖,𝑗 =min{min{dis𝑓𝑟𝑜𝑚,𝑗−1},min{dis𝑓𝑟𝑜𝑚,𝑗 +𝑤}}disi,j=min{min{disfrom,j−1},min{disfrom,j+w}}

其中，𝑓𝑟𝑜𝑚from 表示 𝑖i 的父亲节点，𝑤w 表示当前所走的边的边权．当 𝑗 −1 ≥𝑘j−1≥k 时，dis𝑓𝑟𝑜𝑚,𝑗disfrom,j=∞∞．

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

「JLOI2011」飞行路线

题意：有一个 𝑛n 个点 𝑚m 条边的无向图，你可以选择 𝑘k 条道路以零代价通行，求 𝑠s 到 𝑡t 的最小花费．

参考核心代码：

---|---

* * *

> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/node.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/node.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [mcendu](https://github.com/mcendu), [ouuan](https://github.com/ouuan), [Anguei](https://github.com/Anguei), [Chrogeek](https://github.com/Chrogeek), [Enter-tainer](https://github.com/Enter-tainer), [Henry-ZHR](https://github.com/Henry-ZHR), [hsfzLZH1](https://github.com/hsfzLZH1), [ksyx](https://github.com/ksyx), [MonkeyOliver](https://github.com/MonkeyOliver), [sshwy](https://github.com/sshwy), [Tiphereth-A](https://github.com/Tiphereth-A), [Xeonacid](https://github.com/Xeonacid)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用