HDU1045二分图最大匹配或DFS
在地图中有一些障碍物,同一行或同一列不能放置炮台,否则会互相摧毁,除非有障碍物分隔开。
这题范围小,用DFS不难,不过用二分图匹配十分巧妙。而且数据范围大了DFS应该就不行了。
同一行或同一列不能同时有炮台,和二分图匹配中每个点最多配对一次相对应。
我们将可放置炮台位置的x和y建边,注意被障碍物分隔开的同一行要处理成不同的行,这样跑一边二分图最大匹配就是答案。
DFS代码:
1 | char mp[10][10]; |
二分图匹配代码:
1 | char mp[10][10]; |