web analytics

POJ3020 Antenna Placement 二分图

题目链接:http://poj.org/problem?id=3020

分析:最小路径覆盖.将所有点拆成两个点.建图.做最大匹配.该题最小路径覆盖的答案为:所有点数-最大匹配/2.

Post a Comment

You must be logged in to post a comment.