P2764 最小路径覆盖问题
考虑对于图上的每个节点拆点，拆成入点和出点，所有入点和源点连边，所有出点和汇点连边。
对于原图中的一条边 \((u,v)\)，将 \(u\) 的入点和 \(v\) 的出点连边即可。
答案即为 \(n-\text{maxflow}\)。
网络流刷题笔记
发布时间 2023-11-01 18:20:17作者: Jerry_Jiang
考虑对于图上的每个节点拆点，拆成入点和出点，所有入点和源点连边，所有出点和汇点连边。
对于原图中的一条边 \((u,v)\)，将 \(u\) 的入点和 \(v\) 的出点连边即可。
答案即为 \(n-\text{maxflow}\)。