解题思路 把公路看作边，把城市看作点，被占领的城市看做特殊点，这道题就被转化成求是特殊点相互不联通的最优删减方案。 首先我们换个方向，不删边，改成连边，变为这样一个贪心：先按边权降序排列，然后从前往后枚举所有边，如果某一条边连接后不会使两个特殊点联通，就连上这条边。最后答案为总边权值减去连接过的边权和。 考虑优化时间复杂度： 我们发现，一个连通块中最多有一个特殊点或者没有，我们