现在的位置: 首页 > 综合 > 正文

POJ 2349 Arctic Network

2017年04月28日 ⁄ 综合 ⁄ 共 1435字 ⁄ 字号 评论关闭

题意引用别的:

某地区共有n座村庄,每座村庄的坐标用一对整数(x, y)表示,现在要在村庄之间建立通
讯网络。
• 通讯工具有两种,分别是需要铺设的普通线路和卫星设备。
• 只能给k个村庄配备卫星设备,拥有卫星设备的村庄互相间直接通讯。
• 铺设了线路的村庄之间也可以通讯。但是由于技术原因,通讯距离不超过d。

已知所有村庄的坐标 ( x , y ) ,卫星设备的数量 k 。
 问:如何分配卫星设备,才能使各个村庄之间能直接或间接的通讯,并且 d 的值最
小?求出 d 的最小值。
 数据规模:0 <= k <= n<= 500       (From Waterloo University 2002)

先讲一个应该都知道的概念,根据prim或kuskal的算法

如果连了s条边,那么图中就会有n-s+1个连通块!(一个点也算一个连通块)

嗯,很容易想到,

就是将图连成k个连通块,且用的边尽量小噻,,

连城k个块,很容易的想到了kruskal算法,刚好连到数量符合了直接返回该条边的长度就完美通过了!

看上去是不错的,,但是边数有点多啊。。。

我们再考虑这个问题,根据上述用kruskal的思想同理我们可以先求出一棵树

然后对边进行排序,舍去后面的k-1个边,也可以得解

那么就可以用prim计算树,然后排序之后输出第n-k+1条边(舍去k-1条边后的最大边)

轻松通过~

一遍AC!

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 501
#define INF 1000000000
struct node
{
	int x;
	int y;
}vill[MAX];
double map[MAX][MAX],dist[MAX];
int times,k,n;
double calc(node *a,node *b)
{
	return sqrt((a->x - b->x)*(a->x - b->x)+(a->y - b->y)*(a->y - b->y));
}
void init()
{
	scanf("%d%d",&k,&n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d",&vill[i].x,&vill[i].y);
	}
	for (int i = 1; i <= n; i++)
	for (int j = 1; j  < i; j++)
	{
		map[j][i] = map[i][j] = calc(&vill[i],&vill[j]);
	}
}
void prim()
{
	bool vis[n+1];
	for (int i = 1; i <= n; i++)
	{
		vis[i] = false;
		dist[i] = map[1][i];
	}
	vis[1] = true;
	for (int i = 1; i < n; i++)
	{
		double mini = INF;
		int wh = 0;
		for (int j = 1; j <= n; j++)
		{
			if ( vis[j] == false && mini > dist[j] )
			{
				mini = dist[j];
				wh = j;
			}
		}
		vis[wh] = true;
		for (int j = 1; j <= n; j++)
		{
			if ( vis[j] == false && dist[j] > map[wh][j] )
			{
				dist[j] = map[wh][j];
			}
		}
	}
}
int main()
{
	cin>>times;
	while(times--)
	{
		init();
		prim();
		sort(dist+1,dist+n+1);
		printf("%.2f\n",dist[n-k+1]);
	}
	return 0;
}

抱歉!评论已关闭.