题面 这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了. [collapse title="展开代码"] #include<cstdio> #include<cs…

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

这篇文章受密码保护，输入密码才能阅读