题意引用别的:
某地区共有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; }