DAG 最小路径覆盖问题 笔记

原来我还学过这么个玩意。

一、笔记

P2764 最小路径覆盖问题

首先让 $n$ 个点每个点都是单独的一条路径，接着考虑合并路径。

把每个点拆成只有入度的点和只有出度的点，合并就相当于连接一个只有出度的点和另一个只有入度的点。

显然合并完成后每个拆开的点都最多只能连一条边，合并的次数越多，路径的数目越少，因此转换为二分图最大匹配问题。

答案就是 $n$ 减去最大匹配数。

二、刷题总结

1. P5769 [JSOI2016] 飞机调度

先用 Floyd 预处理出从机场 $i\to$ 机场 $j$ 且在机场 $j$ 休整完毕的最小时间 $f_{i,j}$。一架飞机能执飞航班 $i$ 和航班 $j$（$D_i<D_j$），当且仅当 $D_i+T_{X_i,Y_i}+P_{Y_i}+f_{Y_i,X_j}\le D_j$。把航班看作点，航班之间的关系显然构成 DAG，转换为模板题。