題目鏈接：http://poj.org/problem?id=2349 求最小生成樹(shù)中第S大的邊，結(jié)點(diǎn)給的是坐標(biāo)（坑爹啊 ）
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 500
9 struct edge
10 {
11 int u, v;
12 double w;
13 }e[250000];
14 struct data
15 {
16 int x, y;
17 }a[N];
18 int S, P, tot, cnt, p[N];
19 double dis(data a, data b)
20 {
21 int x = a.x - b.x;
22 int y = a.y - b.y;
23 double xx = x * x;
24 double yy = y * y;
25 return sqrt(xx + yy);
26 }
27 int find(int x)
28 {
29 return p[x] != x ? p[x] = find(p[x]) : x;
30 }
31 void add(int x, int y, double z)
32 {
33 tot++;
34 e[tot].u = x;
35 e[tot].v = y;
36 e[tot].w = z;
37 }
38 double cmp(double a, double b)
39 {
40 return a > b;
41 }
42 double cmp2(edge a, edge b)
43 {
44 return a.w < b.w;
45 }
46 int main()
47 {
48 int r1, r2, t;
49 double ans, w[250000];
50 cin >> t;
51 while (t--)
52 {
53 cin >> S >> P;
54 for (int i = 0; i < P; i++) p[i] = i;
55 tot = ans = cnt = 0;
56 memset(e, 0, sizeof(e));
57 memset(w, 0, sizeof(w));
58 for (int i = 0; i < P; i++) scanf("%d%d", &a[i].x, &a[i].y);
59 for (int i = 0; i < P; i++)
60 for (int j = 0; j < P; j++)
61 {
62 if (i != j) add(i, j, dis(a[i], a[j]));
63 }
64 sort(e + 1, e + 1 + tot, cmp2);
65 for (int i = 0; i < tot; i++)
66 {
67 r1 = find(e[i].u); r2 = find(e[i].v);
68 if (r1 != r2)
69 {
70 p[r2] = r1; w[cnt++] = e[i].w;
71 }
72 }
73 sort(w, w + cnt, cmp);
74 if (S == 0) ans = w[0];
75 else ans = w[S - 1];
76 printf("%.2lf\n", ans);
77 }
78 return 0;
79
|