用kruskal + LCA如何保证严格次小?
查看原帖
用kruskal + LCA如何保证严格次小?
835255
_cheng楼主2024/8/18 16:49

如题,提供一个Hack如下:

7 15
6 3 35
1 6 44
3 2 22
2 7 57
5 1 57
5 6 65
5 3 44
7 4 57
7 2 44
7 1 44
4 5 44
4 5 44
2 3 65
1 7 44
1 2 44

用自动画图器画出来后,发现,枚举到边2→12→1时,两个端点的树上路径的最大值为4444,程序会将边2→12→1换成边6→16→1,发现不是严格次小,就排除了。

然而答案并非如此。答案是将边2→12→1换成边6→36→3,这比换成任何其它边更优。但程序只能找出两端点之间的最大值,而不是次大值,就无法找出Test#4的答案。

所以有什么办法解决吗qwq

2024/8/18 16:49
加载中...