首页 > 其他 > 详细

GDOI2018D2T1 谈笑风生

时间:2019-02-03 15:52:35      阅读:161      评论:0      收藏:0      [点我收藏+]

T1 谈笑风生

【题目描述】

技术分享图片

【输入】

技术分享图片

【输出】

一行两个数,所需能量P与在能量最小的前提下最短的到达时间t。

【样例输入】

5 7 66
4 3 2 1 5
1 2
1 5
2 3
2 4
2 5
3 4
3 5

【样例输出】

6 64

【数据范围限制】

技术分享图片

【样例解释】

从城市1出发,花费6单位能量,依次经过2、4、3、到达首都5,花费32+3+0+29=64秒

Solution

边权计算规则
\[ w=\sum_{i=1}^{num[u]}\sum_{j=1}^{num[v]}(i+j)[(i,j)=1] \]

\[ \begin{aligned} &设sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}(i+j)\w&=\sum_{i=1}^{num[u]}\sum_{j=1}^{num[v]}(i+j)[(i,j)=1]\&=\sum_{i=1}^{num[u]}\sum_{j=1}^{num[v]}(i+j)\sum_{k|(i,j)}\mu(k)\&=\sum_{k=1}^{min(num[u],num[v])}k\mu(k) \sum_{i=1}^{\lfloor\frac{num[u]}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{num[v]}{k}\rfloor}(i+j)\&=\sum_{k=1}^{min(num[u],num[v])}k*\mu(k)*sum(\lfloor\frac{num[u]}{k}\rfloor,\lfloor\frac{num[v]}{k}\rfloor) \end{aligned} \]

易得
\[ \begin{aligned} sum(n,m)&=\sum_{i=1}^{n}\sum_{j=1}^{m}(i+j)\&=\frac{nm(n+m+2)}{2} \end{aligned} \]
所以可以\(m\sqrt{max(num[i])}\)的计算出每条边的边权

然后二分答案+spfa计算即可。

因为JZOJ不开放注册。。。所以就没办法交了,口胡一波,题面还是网上找来的。。。

不过思路是对的。好像GDOI2018我也就两道T1会写T_T

GDOI2018D2T1 谈笑风生

原文:https://www.cnblogs.com/henry-1202/p/10350445.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!