娱乐 每 日 算 法 挑 战 （大嘘）【第0x17期】

[yhz012]

附加题至少有一些预处理可以做

给定有向图，那首先可以获取给定顶点的强连通部分strongly connected components，任何包含这个顶点的环必然只在这个部分里

 

说起来题目要求简单环么，如果要求的话，甚至可以根据双联通bi-connected再砍一次？

五月 8, 2020，由yhz012修改

[yhz012]

26 分钟前, Mr.K 018 说道:

原则上没有

那最坏情况是在强连通部分暴搜所有环，然后判断环是否包含该顶点……

[yhz012]

16 小时前, PhoeniXLL 说道:

比如先预期一个答案x, 把图里每条边都减掉x, 这时候如果你能找到一个过这个点的负环就说明还有优化空间, 那就继续降低x, 反之提高x

如果不要求简单环那么其实这个限定过某点的限制就有些无力(因为会找到一个和这个点在同一个强联通分量里权值最小的环疯狂转圈), 所以我才问是不是要求简单环但简单环我又不会

所以这个算法的推论是，均值最后会趋于强连通分量的最小均值环（无论是否包含该顶点）？

全图-x这个做的是真的漂亮

五月 8, 2020，由yhz012修改