POJ 2594 Treasure Exploration (最小路径覆盖)

机器人在图上走,用最少的机器人走遍全图,图是单向无环图。

最小路径覆盖,存在路径之间有公共点,所以先对原图求一下闭包,然后对处理后的图拆点跑最大匹配。

 

 

LEAVE A COMMENT