P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd;

记住:大胆假设,不用证明

先存图,观察数据范围n <= 50 ,直接用floyd求出最短路。

继续二分最大长度 c ,对于每个已有城堡的城市,直接去标记其能到达的城市,然后对于不能到达的,

我们将其距离不超过枚举的c的点期望 + 1,分别在k次中每次找到最大期望的值进行建城堡。

最后看看还有没有点无法到达,搞定。

c++代码如下:

 

9 + 2 =