拆点

拆点不是一种具体算法，而是一种图论中的重要思想，样用于网络流，用来处理点权或者点的流量限制问题，也适用于分层图

结点有流量限制的最大流

把一个节点 $u$ 拆成两个节点 $u,u'$ 然后 $u$ 承载别的连到这个点的边，$u'$ 往别的节点练边

原图是这样的

拆点后是这样的

分层图最短路

看一个例题

洛谷 P4568「JLOI2011」飞行路线 (opens new window)

有 $k$ 次零代价通过一条路径，求总的最小花费

我们可以采用 DP 思想，定义 $dis[i][j]$ 表示从起点到 $i$，使用看 $j$ 次免费通行权限后的最短路径，显然转移方程为

$dis[i][j]=\min\{\min \{dis[from][j-1] \},\min \{ dis[from][j]+w \}\}$

其中 $from$ 为 $i$ 的父节点，$w$ 为这条路的边权，当 $j-1\le k$ 时，$dis[from][j]=INF$

实际上，这个 DP 就相当于把每个节点拆成了 $k+1$ 个节点，然后在分层图上跑最短路