原来我还学过这么个玩意。
一、笔记
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，转换为模板题。