poj 2594 Treasure Exploration (DAG图最小路径覆盖变形,匈牙利算法+floyd求传递闭包)

poj 2594 题目链接

题意:一个DAG图,每个点有宝藏...可以降落任意个机器人到任意点...然后机器人可以沿着路径走,路过某个点的时候,可以取走该点的宝藏。问要取走所有宝藏,最少需要多少个机器人。

思路:乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候,可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point.

那是否还可以用最小路径覆盖做呢。。答案是可以的。。。

区别就在于一个点如果被一条路径使用过一次,还可不可以使用第二次。。。

如果我们按照传统的DAG图的最小路径覆盖考虑。。。如果一个点会被路径经过两次。。。那么我们不妨增加一个点。。。 进一步考虑。。。我们要的是尽可能覆盖所有点。。。如果这条路径前后的点不会因为这个点而中断,那么这个增设点是否存在,其实是无所谓的,只要改点前后的点连通性不受影响即可。 说到连通性,不禁想到floyd求传递闭包。

然后对于DAG图的最小路径覆盖问题。。。就可以用hungary算法求解。。。

ans = n - 最大匹配数。

这应该算作hungary的一个应用。