Tag-最小生成树

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-03-24 23:21:38 |  0 Comments  |  最小生成树

UvaLive-6437 Power Plant(变种Kruskal)

UVALive-6437

题外话

还是vjudge不错233,可以不用注册新帐号了。

这是本人第一篇关于Uva题目的题解。

题目链接放上面大家自己去点,因为PDF格式真的是粘不过来。

题目大意

现在有n个城市,城市之间有m个预期修筑电缆的方案线,其中有k个城市有发电站。

现在要求建设电线,使得每个城市都能有供电。由于每条线路有一定的花费,所以现在要求满足题目的最小花费。

题解

其实题目里已经简化成一个图了,剩下的就是自己想该怎么解决了。

其实思考一下,这好像跟用最小代价选边使得图连通的问题非常接近,第一感觉就是个最小生成树啊,直接kruskal或者Prim就行了啊。

但是回过头来想想,好像有那么一点不对劲的地方。

你看那个样例演示图,明明是不连通的啊。

这是因为本身就有发电站的城市不一定要跟外部连通。所以这题就不是一个纯粹的最小生成树了。但是还是很像,所以我们选择对kruskal进行一下修改。

记录一个cnt,表示当前供上电城市的数量,并查集跟普通kruskal一样的路径压缩写法,不过要加上一个siz数组来记录这一个并查集里有多少城市。

排序也和正常的kruskal一样。

关键点来了。

如何合并并查集啊?以及cnt怎么更新啊?

由于本身就有发电站的城市不一定要和外部连通,所以我们这样:

定义当前边的两个端点的父亲(并查集find后)为x,y,分以下三种情况:

1.x,y都不是有发电站的城市:直接合并并查集,f[y] = x;siz[x] += siz[y];ans(总花费) += dis。

2.x,y都是有发电站的城市:直接跳过,不需要这条边,也不计入答案。

3.x为有发电站的城市,y则是没有发电站的城市:将y所在的并查集合入x所在的并查集内,维持x在并查集的根节点的位置,并更新当前已经有供电的城市数cnt。

f[y] = x;siz[x] += siz[y];ans += dis;cnt += siz[y];

cnt的初值就是赋为k,表示一开始共有k个城市有供电。

这样这个问题就很轻松的解决了。

为什么不选择Prim?因为Prim没有像Kruskal这样顺手的并查集啊QAQ。(好吧实际上是我Kruskal打习惯了)

参考代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
	int num = 0;
	char c;
	bool flag = f
Title - Artist
0:00