一道信息图论题
答案:1 悬赏:10 手机版
解决时间 2021-03-24 09:06
- 提问者网友：沦陷
- 2021-03-23 18:44
一道信息图论题
最佳答案
- 五星知识达人网友：迷人又混蛋
- 2021-03-23 19:17
令路径上的边的集合为S
答案就是(∑(i∈S）vi)/∑(i∈S)1
二分答案，设答案为x
(∑(i∈S）vi)/∑(i∈S)1>=x
(∑(i∈S）vi)>=∑(i∈S)x
∑(i∈S）(vi-x)>=0
然后可以dp一下u,v之间每条边权-x之后的最长路，判断一下
答案就是(∑(i∈S）vi)/∑(i∈S)1
二分答案，设答案为x
(∑(i∈S）vi)/∑(i∈S)1>=x
(∑(i∈S）vi)>=∑(i∈S)x
∑(i∈S）(vi-x)>=0
然后可以dp一下u,v之间每条边权-x之后的最长路，判断一下
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯