pku1422 Air Raid

在一个P*P的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次），由上面可以得出：

 

１.一个单独的顶点是一条路径；

２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边。

 

其中二分图的构造是把原图中的每个顶点pi分成两个顶点pi'与pi''，如果在原图中存在一条pi到pj的边，那么在二分图中就有一条连接pi'与pj''的无向边；这里pi' 就是原图中该边的出点pi，pj''就是原图中该边的入点pj，然后求出二分图的最大匹配。。。若匹配数为0，则说明任意pi'和pj''之间都没边相连，对应于原图说明任意pi和pj之间都没有路径可达，那么每个单独的点就是一条路径；若每增加一条匹配边pi'->pj''，则说明原图中pi和pj之间可以共存在一条路径上，那么所需要的路径数目就减1，由于匹配中的每条边都没有交点，并且这题明确说明在小镇间不会构成回路，这样随着匹配数的增多，原来单独的顶点会被不断整合到由匹配边所连接的那条路径上，也就是说某一条路径所覆盖的点数会不断增多，而且不同的路径之间若没有匹配边也就不会合并，这样最大匹配数对应最小路径覆盖数。。。

 

最小路径覆盖＝|P|－最大匹配数。。。