Processing math: 100%
[Codeforces Round #445][Codeforces 886D]Restoration of string
[Codeforces Round #447][Codeforces 894C]Marco and GCD Sequence

[Codeforces Round #447][Codeforces 894E]Ralph and Mushrooms

Zarxdy34 posted @ 2017年11月20日 09:34 in Codeforces with tags 强联通分量 Tarjan , 452 阅读

    题意:给出一个有向图,对于一条边i,其初始权值为wi,第一次经过该边获得wi的权值,第二次经过该边获得wi1的权值,第三次为wi12,第四次wi123,直到该边权值减到<=0之后,经过该边不再获得任何权值。从起点s出发,求一条能获得最大权值和的路径,输出获得的最大权值和。其中wi<=108,1<=n<=106,0<=m<=106

    题解:考虑到在一个强联通分量内的点间的路径肯定是全部用完是最优的,所以可以先强联通分量缩点,然后图就变成了一棵树,树上路径一定最多经过一次。剩下要求的就是一个强联通分量中所有路径用完的权值,即每条路径用完的权值和。这个写出式子求个和就好了,比较简单就不写了。

    PS:由于数据量是106级别的,所以如果重构图要去重边的话不能带log,否则会TLE。(来自Div2 FST选手的怨念)(当然不用删重边够做了)

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter