Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其它的小岛时都要通过划小船来实现。

如今政府决定大力发展百岛湖。发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！

经过考察小组RPRush对百岛湖的情况充分了解后。决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。

当然，为了节省资金。仅仅要求实现随意2个小岛之间有路通就可以。当中桥的价格为 100元/米。

 

Input

输入包含多组数据。输入首先包含一个整数T(T <= 200)，代表有T组数据。

每组数据首先是一个整数C(C <= 100),代表小岛的个数。接下来是C组坐标。代表每一个小岛的坐标。这些坐标都是 0 <= x, y <= 1000的整数。

 

Output

每组输入数据输出一行，代表建桥的最小花费。结果保留一位小数。假设无法实现project以达到所有畅通，输出”oh!”.

 

Sample Input

2

2

10 10

20 20

3

1 1

2 2

1000 1000

 

Sample Output

1414.2

oh!

 

Author

8600

 

Source

field=problem&key=2008%D5%E3%B4%F3%D1%D0%BE%BF%C9%FA%B8%B4%CA%D4%C8%C8%C9%ED%C8%FC%A3%A82%A3%A9%A1%AA%A1%AA%C8%AB%D5%E6%C4%A3%C4%E2&source=1&searchmode=source" style="color:rgb(26,92,200); text-decoration:none">2008浙大研究生复试热身赛（2）——全真模拟

 

AC代码：

kruskal：

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<algorithm>

using namespace std;

int per[111];

double x[111],y[111];

struct node{

	int start,end;

	double distance;

};

node p[10000];

int cmp(node a,node b)	//距离从小到大

{

	return a.distance < b.distance;

}

void init()

{

	for(int i = 1;i < 111;i++ )

		per[i] = i;

}

int find(int x)

{

	if(x == per[x])

		return x;

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

}

bool join(int x,int y)

{

	int fx = find(x);

	int fy = find(y);

	if(fx != fy)  //推断是否成环

	{

		per[fx] = fy;

		return true;  //没成环

	}

	return false;

}

int main()

{

	int i,j,k;

	int t,n,c;

	double d,cost;  //一定要注意题目所要求的数据类型

	scanf("%d",&t);

	while(t--)

	{

		init();

		scanf("%d",&c);

		for(i = 1;i <= c; i++)

		{

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

		}

		k = 0;

		for(i = 1;i <= c;i++)

		{

			for(j = i+1;j <= c;j++)

			{

				d = sqrt( (x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]) );//距离公式

				if(d >=10.0 && d <= 1000.0)	//一定要筛选完再存进结构体 要不然会WA.

				{

					p[k].start = i;   //起点

					p[k].end = j;	  //终点

					p[k].distance = d;//起点到到终点的距离

					k++;

				}

			}

		}

		sort(p,p+k,cmp);   //按距离从小到大排序

		int num = 0;

		cost = 0.0;

		for( i = 0;i < k; i++)

		{

			if(join(p[i].start, p[i].end))

			cost += p[i].distance;

		}

		for( i = 1;i <= c;i++ )

		{

			if(per[i]==i)

			num++;

			if(num > 1)		// 及时跳出循环节省时间

			break;

		}

		if(num>1)  //无法连接全部小岛

			printf("oh!\n");

		else

			printf("%.1lf\n",100*cost);

	}

	return 0;

}

===============================切割线======================================

prim：

#include<cstdio>

#include<cstring>

#include<cmath>

#define mem(a, b) memset(a, (b), sizeof(a))

#define Wi(a) while(a--)

#define Si(a) scanf("%d", &a)

#define Pi(a) printf("%d\n", (a))

#define Pf(a) printf("%.1lf\n", (a))

#define INF 0x3f3f3f

double map[150][150];

int x[150],y[150];

int n;

double d[150], vis[150];

void prim()

{

	mem(vis, 0);

	int i, j, k;

	double ans = 0, minn;

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

		d[i] = map[1][i];

	vis[1] = 1;

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

	{

		k = 1;

		minn = INF;

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

		{

			if(!vis[j] && d[j] < minn)

			{

				minn = d[j];

				k = j;

			}

		}

		if(minn == INF){

			puts("oh!");return;

		}

		vis[k] = 1;

		ans += minn;

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

		{

			if(!vis[j] && d[j] > map[j][k])

				d[j] = map[j][k];

		}

	}

	Pf(ans*100);

}

int main(){

	int t; Si(t);

	Wi(t){

		Si(n);

		int i , j, k;

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

		{

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

		}

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

		{

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

			{

				double d = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));

				if(d >= 10.0 && d <= 1000.0)

					map[i][j] = map[j][i] =  d;

				else

					map[i][j] = map[j][i] = INF;

			}

			map[i][i] = 0;

		}

		prim();

	}

	return 0;

}