Bzoj 1821(最小生成树)

BZOJ 1821
平面上给点询问边权问题一般是最小生成树。
我们把点一一存边,然后最小生成树加边,加到有$k$个连通分量后,输出下一条能够使联通分量增加的边的边权即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5;
int en, n, k, f[MAXN];
struct pos {int x, y;}p[MAXN];
struct data {
int u, v;
db dist;
bool operator < (const data &b) const {
return dist < b.dist;
}
}e[MAXN * MAXN];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
db getDist(pos &a, pos &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void clean() {
en = 0;
for (int i=1;i<=n;i++) f[i] = i;
}
void solve() {
clean();
for (int i=1;i<=n;i++) {
scanf("%d%d", &p[i].x, &p[i].y);
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
en++;
e[en].u = i, e[en].v = j, e[en].dist = getDist(p[i], p[j]);
}
}
sort(e + 1, e + 1 + en);
int tot = 0;
for (int i=1;i<=en;i++) {
int x = find(e[i].u), y = find(e[i].v);
if (x == y) continue;
f[x] = y;
tot++;
if (tot > n - k) {printf("%.2f\n", e[i].dist); return ;}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &k), solve();
return 0;
}

------ 本文结束 ------