记录一下跑最小生成树时的边就行了。
原理是一样的
by C20203030 @ 2021-03-28 08:45:03
@[C20203030](/user/128239) 但是替换怎么做呢
by pocafup @ 2021-03-28 08:46:00
输出方案好像一直都是 wqs 二分的难点？
by SSerxhs @ 2021-03-28 08:47:21
~~可能是我没学懂吧~~
by C20203030 @ 2021-03-28 08:55:40
@[pocafup](/user/219099) 方案唯一的时候是记录一下选了哪些边就行。那么微扰一下边权就可以保证方案唯一了吧。
by tommy0221 @ 2021-03-28 10:53:28
@[tommy0221](/user/123384) 微扰一笑边权是怎么样啊
就比如现在二分到的边界为 $r$，这时候黑边 < need, 但 r+1 时会黑边 > need。这时候虽然可以通过将替换边界边权的白边黑边，但是怎么确认替换哪几条边呢
by pocafup @ 2021-03-28 14:30:47
@[pocafup](/user/219099) 就是一读入进来就给每一条边加个的 $10^{-7}$ 左右的随机权值（参数要自己调）然后跑实数域上的wqs二分，这样子可以保证刚好切到凸包上的一个点，然后直接输出选了哪些边即可。
by tommy0221 @ 2021-03-28 14:39:51
@[tommy0221](/user/123384) 可能我还没学懂我自己理解一下吧
Orz
by pocafup @ 2021-03-28 15:10:22