畅通工程再续

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 37615    Accepted Submission(s): 12574

Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在*决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，*决定实现百岛湖的全畅通！经过考察小组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!

思路

把所有的点之间的距离都求出来，将两个点的标号和距离都存到一个结构体中，然后套用最小生成树的模板就行了

AC代码

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x3f3f3f3f

const double E=exp(1);

const int maxn=10000+10;

using namespace std;

double f[maxn];

double x[maxn],y[maxn];

struct wzy

{

	double first,end;

	double cost;

};

bool cmp(wzy u,wzy v)

{

	return u.cost<v.cost;

}

int find(int x)

{

	if(x==f[x])	return x;

	return f[x] = find(f[x]);

}

bool join(int x,int y)

{

	int dx=find(x);

	int dy=find(y);

	if(dx!=dy)

	{

		f[dx]=dy;

		return true;

	}

	return false;

}

int main(int argc, char const *argv[])

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

		wzy r;

		vector<wzy>d;

		ms(x);

		ms(y);

		int n;

		scanf("%d",&n);

		for(int i=0;i<=n;i++)

			f[i]=i;

		for(int i=0;i<n;i++)

			scanf("%lf%lf",&x[i],&y[i]);

		for(int i=0;i<n-1;i++)

		{

			for(int j=i+1;j<n;j++)

			{

				r.first=i;

				r.end=j;

				r.cost=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

				if(r.cost<=1000.0&&r.cost>=10.0)

					d.push_back(r);

			}

		}

		if(d.size()==0)

		{

			printf("oh!\n");

			continue;

		}

		sort(d.begin(),d.end(),cmp);

		double sum=0.0;

		int flag=0;

		for(int i=0;i<d.size();i++)

		{

			if(join(d[i].first,d[i].end))

			{

				flag++;

				sum+=d[i].cost;

			}

		}

		int num=0;

		for(int i=0;i<n;i++)

		{

			if(f[i]==i)

				num++;

		}

		if(num!=1)

			printf("oh!\n");

		else

			printf("%.1lf\n",sum*100.0);

	}

	return 0;

}