Luogu 2764 – 最小路径覆盖问题

题目链接:洛谷 2764 或 LOJ 6002

用最少的路径覆盖图上所有的点,并且路径与路径之间不能有公共边。(这里的路径是指图上的若干个点和边构成的链,一个点也是一条路径)

考虑二分图中:

$$ C_{\min} = |V| – M $$

其中,$C_{\min}$为最小路径覆盖,$|V|$为顶点数,$M$是二分图最大匹配数。

可以这样理解:整张图全是点没有边的时候,很显然如果点的个数是$n$,那么路径数就是$n$,每个点自成一条路径,这个式子显然成立;接着在二分图中每增加一条边,会连接一个左部的点和一个右部的点,那么这两个点原来属于两条路径,现在属于一条路径,那么路径覆盖减少1;由此可以得到在二分图达到最大匹配的时候是路径覆盖最小。可以用网络流跑二分图匹配。

路径的输出可以直接通过匹配的边建一张新图,然后从入度为0的点开始dfs。

坑点:maxn要开两倍n的大小。

 

说点什么

avatar
50
  Subscribe  
提醒