标签:SPFA

OI

[POJ3268]Silver Cow Party[SPFA]

cgazn阅读(136)评论(0)赞(0)

题面 这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了.

OI

[HNOI2009]最小圈[0/1分数规划,SPFA]

cgazn阅读(198)评论(0)赞(0)

题面 标题比题面好懂系列. 题目就是要求所有环中边权之和与环长之比的最小值. 令点权为1(方便统计长度. 更一般的0/1分数规划题中点权是可以任意取的, 后续推导一致), 则 $latex ans=\sum{e.w}/\sum{v.w}$ ...