Rockdu's Blog

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;
}