icontofig | 发布于 2019-03-24 23:21:38 | 阅读量 242 | 最小生成树
发布于 2019-03-24 23:21:38 | 最小生成树
UVALive-6437 题外话还是vjudge不错233,可以不用注册新帐号了。 这是本人第一篇关于Uva题目的题解。 题目链接放上面大家自己去点,因为PDF格式真的是粘不过来。 题目大意现在有n个城市,城市之间有m个预期修筑电缆的方案线,其中有k个城市有发电站。 现在要求建设电线,使得每个城市都能有供电。由于每条线路有一定的花费,所以现在要求满足题目的最小花费。 题解其实题目里已经简化成一个图了,剩下的就是自己想该怎么解决了。 其实思考一下,这好像跟用最小代价选边使得图连通的问题非常接近,第一感觉就是个最小生成树啊,直接kruskal或者Prim就行了啊。 但是回过头来想想,好像有那么一点
继续阅读