威风镰鼬

分类

题解(153)

/ 注册

全部文章（共1篇）

题解 | #Desert King#

思路分数规划问题。我们可以求得每两个村子的距离和花费，然后列举最大的ans使得∑（costi−ans∗leni）=0\sum （cost_i-ans*len_i）=0 ∑（costi−ans∗leni）=0 我们固定住1号作为根节点，只需要建一棵最小生成树，二分答案即可求出。（每个点都是与最...

最小生成树 MST 分数规划二分

2021-11-16

1 293