发布时间：2024-07-31

最小路径点覆盖：用最少的互不相交的路径将点覆盖

针对DAG(有向无环图)

• 拆点，如果一条路径i->j，那么i的出点连向j的入点
• 对于路径终点，其没有出边，因此为左部的非匹配点
• 即让左部非匹配点尽可能少，左部匹配点尽可能多，记为m,答案即n-m