期望 – Tgotp-Blog

P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd;

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

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

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

我们将其距离不超过枚举的c的点期望[......]

Read more