本文共 250 字,大约阅读时间需要 1 分钟。
拆点就是将一个点拆成入点和出点两个点,并在两个点之间建一条边。
拆点是为了实现对点的限制。
如第二点,当题目中明确说明对点有限制或在实际应用中对点有限制时,我们就需要拆点。例如我们要保证经过某点中转的流量不能大于5(对点有流量限制),那么我们就需要将该点拆成入点和出点,并在两点间建一条容量为5的边,就实现了对点的限制。
做题时一定要看清,如果是对边有限制,就通过流量或流网络来实现;如果是对点有限制,就通过拆点来实现。
转载地址:http://hfbki.baihongyu.com/