首页 > Desert King
开通博客写题解
头像 威风镰鼬
发表于 2021-11-16 15:31:52
思路 分数规划问题。我们可以求得每两个村子的距离和花费，然后列举最大的ans使得∑（costi−ans∗leni）=0\sum （cost_i-ans*len_i）=0 ∑（costi​−ans∗leni​）=0 我们固定住1号作为根节点，只需要建一棵最小生成树，二分答案即可求出。 （每个点都是与最 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”