[THUSC2017]巧克力[斯坦纳树、随机化]

时间:2023-03-09 17:42:27
[THUSC2017]巧克力[斯坦纳树、随机化]

题意

题目链接

分析

  • 对于第一问,如果颜色数量比较少的话可以 \(\binom{cnt}{k}\) 枚举最终连通块中的 \(k\) 种颜色,然后利用斯坦纳树求解。
  • 如果颜色比较多,考虑将所有的颜色重新随机赋值 \([0,k-1]\) 然后跑斯坦纳树。貌似还可以证明:最终的连通块中一定恰好只有 \(k\) 种颜色。那么只要最终答案中那 \(k\) 种颜色随机到的是不同的颜色,就可以跑出正确答案,成功的概率是 \(\frac{k!}{k^k}\) ,而且最优解还可能不唯一,所以做 100 次失败的概率就大概只有 \(1\%\) 了。
  • 考虑第二问,首先二分一个答案 \(mid\) ,然后将所有 \(\le mid\) 的权值设置成 -1 ,否则设置成1,比较的时候就比较一个二元组(点数,权值和)即可。也容易证明这样的比较方式在我们使用 \(dijkstra\) 时仍然是正确的。

代码

代码链接