ZJU/ZOJ 1525 Air Raid 解题报告

题目大意是在一个有向无环图中，每个士兵可以从一个路口一直往前走，经过的路口即可被占领，问占领所有路口最少需要派遣多少士兵。

也就是求有向无环图的最小路径覆盖。这是一个非常经典的模型，可以转化为二分图最大匹配。构图方法是如果从a到b存在一条单向边则在二分图中Xa到Yb连上一条边，则最小路径覆盖=总顶点数-二分图最大匹配。

3014660 2008-07-30 21:36:18 Accepted 1525 FPC 00:00.02 420K IwfWcf@LZOI