POJ2594 Treasure Exploratio 二分图匹配+floyd求闭包

题意为给你一张有向图,可以从很多点派出很多机器人,机器人可以一直顺着边走,问至少几个机器人才能遍历所有的点。

显然这是求最小路径覆盖,而且有可能有边相交的情况,所以我们先跑一遍floyd求闭包,然后在进行二分图匹配,最后输出点数-最大匹配即可。

注意处理多case情况

发表评论