UVA 10369- Arctic Network(最小生成树)
UVA 10369- Arctic Network(最小生成树)
题目大意:北极有n个前哨点,如果两个前哨点都有安装无线卫星,那么它们就可以互相通信,然而现在只有m - 1 个前哨点安装了无线卫星,其余的n - m + 1 个航哨点就需要安装有线,有线的成本和之间的距离成正比,所以要求你找出最小的d(两个前哨点之间的距离),能够使得任意的前哨点之间可以通信。
解题思路:最小的d,也就是满足条件的最小的两点之间的距离。用kruskal做,然后已经有m - 1个点已经可以互相通信了,那么就只需要再连接n - m + 1个点,就有n - m条边,从小到大排序边,只要找到第n - m大的接入边就是最小的d。
代码:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 505;
const int maxm = 300000;
int u[maxm], v[maxm], r[maxm];
int p[maxn];
double w[maxm];
struct Node {
int x, y;
}node[maxn];
double dist (int i, int j) {
double x = node[i].x - node[j].x;
double y = node[i].y - node[j].y;
return sqrt(x * x + y * y);
}
void init (int n, int cnt) {
for (int i = 0; i < n; i++)
p[i] = i;
for (int i = 0; i < cnt; i++)
r[i] = i;
}
int getParent (int x) {
return (x == p[x]) ? x : p[x] = getParent(p[x]);
}
int cmp (int i, int j) {
return w[i] < w[j];
}
double Kruskal (int n, int cnt, int m) {
init(n, cnt);
sort(r, r + cnt, cmp);
int flag = n - m;
double ans;
for (int i = 0; i < cnt; i++) {
int P = getParent(u[r[i]]);
int Q = getParent(v[r[i]]);
if (P == Q) continue;
if (flag--) {
ans = w[r[i]];
p[P] = Q;
} else
return ans;
}
return ans;
}
int main () {
int T;
scanf ("%d", &T);
int n, m;
while (T--) {
scanf ("%d%d", &m, &n);
for (int i = 0; i < n; i++)
scanf ("%d%d", &node[i].x, &node[i].y);
int pos = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
u[pos] = i;
v[pos] = j;
w[pos++] = dist(i, j);
}
printf ("%.2lf\n", Kruskal(n, pos, m));
}
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。