P1550 [USACO08OCT] Watering Hole G 分析

· · 个人记录

最开始考虑的是把 dis 初值设为挖井的代价，还兴致勃勃打了一大堆 Prim，最后发现狗屁不通。

看了一眼第一篇题解茅塞顿开。我们可以将“挖井”的操作看成是与地下相连。权重就是挖井的代价。Kruskal 即可。