UvaLive-6437 Power Plant(变种Kruskal)

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

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 = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = num * 10 + c - '0';
	return (flag ? -1 : 1) * num;
}
int T,n,m,k;
const int maxn = 205;
struct edge{
	int fr,to,dis;
	bool operator < (const edge &b) const {
		return this->dis < b.dis;
	}
}e[maxn*maxn];
int f[maxn];
int siz[maxn];
int find(int x){
	if(f[x] != x)f[x] = find(f[x]);
	return f[x];
}
int cnt;
int x;
bool vis[maxn];
int main(){
	T = get_num();
	for(int cas = 1;cas <= T;++cas){
		int ans = 0;
		n = get_num();
		m = get_num();
		k = get_num();
		memset(vis,0,sizeof(vis));
		for(int i = 1;i <= n;++i)
			f[i] = i,siz[i] = 1;
		for(int i = 1;i <= k;++i){
			x = get_num();
			vis[x] = true;
		}
		for(int i = 1;i <= m;++i){
			e[i].fr = get_num();
			e[i].to = get_num();
			e[i].dis = get_num();
		}
		cnt = k;
		sort(e+1,e+m+1);
		int now = 1;
		while(cnt != n){
			int x = e[now].fr;
			int y = e[now].to;
			x = find(x);
			y = find(y);
			if(x == y){
				now++;
				continue;
			}
			if(vis[x] && vis[y]){
				now++;
				continue;
			}
			if(!vis[x] && !vis[y]){
				f[y] = x;
				siz[x] += siz[y];
				ans += e[now].dis;
			}
			else{
				if(vis[y])swap(x,y);
				ans += e[now].dis;
				f[y] = x;
				siz[x] += siz[y];
				cnt += siz[y];
			}
			now++;
		}
		printf("Case #%d: %d\n",cas,ans);
	}
	return 0;
} 


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00