1566G

交了整整 2 页，本来想用随机化卡过去的，后来发现我的实现跑得太慢就写正常做法了。 首先发现最优答案对应的四个点只可能有以下两种可能： - $a,b$ 间有边，$c,d$ 间有边，此时答案是 $a,b$ 边权值加 $c,d$ 边权值。 - $a$ 与 $b,c,d$ 三个点间都有边，此时答案是三条边 ......