HDU1875 畅通工程再续
? 解题记录 ? ? HDU ? ? 补档计划第一期 ? ? Kruscal ?    2017-10-01 14:14:44    549    0    0

相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

Input

输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。 
每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是 0 <= x, y <= 1000的整数。 
Output

每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。如果无法实现工程以达到全部畅通,输出”oh!”.

Sample Input

2
2
10 10
20 20
3
1 1
2 2
1000 1000

Sample Output

1414.2
oh!​

很简单的一道最小生成树,比较适合作为模板题。只需要对不合格的边进行处理跑一遍Kruscal就行了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const int maxn=110;
struct edge
{
	int u,v;
	int w;
	bool operator <(const edge &a) const
	{
		return w<a.w;
	}
}e[maxn*maxn];

struct node
{
	int x,y;
}nodes[maxn];

int fa[maxn]={ };
void init(int n)
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
}

int find(int a)
{
	if(fa[a]==a) return a;
	return fa[a]=find(fa[a]);
}

void combine(int x,int y)
{
	x=find(x);y=find(y);
	fa[x]=y;
}

int cntdis(node a,node b)
{
	return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int n,num_e,t;

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		num_e=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d%d",&nodes[i].x,&nodes[i].y);
		
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)//处理边 
			{
				int mid=cntdis(nodes[i],nodes[j]);
				if(mid<100 || mid>1000000)
					continue;
				num_e++;
				e[num_e].w=mid;
				e[num_e].u=i;
				e[num_e].v=j;
			}
		}
		
		sort(e+1,e+num_e+1);
		int cnt=0;
		double ans=0;
		init(n);
		for(int i=1;i<=num_e;i++)
		{
			if(find(e[i].u)!=find(e[i].v))
			{
				cnt++;
				ans+=sqrt(e[i].w);
				combine(e[i].u,e[i].v);
			}
			if(cnt==n-1)
				break;
		}
		if(cnt<n-1)
			printf("oh!\n");
		else
			printf("%.1lf\n",ans*100);
	}
	return 0;
}

上一篇: BZOJ1787 Meet 紧急集合

下一篇: 洛谷P3384 【模板】树链剖分

549 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航