POJ2253 的 Kruskal 做法

发表于 分类于

许多分类，把这题分到了最短路里面，也看过一些用 Floyd、SPFA 的写法，但是我觉得，这题没必要想太复杂，直接建立最小生成树，在建树的过程中，如果加入了一条边，使得起点和终点连通了，那么这条边一定是最大的那条，也就是答案。

我的代码如下，每次加入一条边，判断 0、1 的连通性。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

struct Edge {
  int from;
  int to;
  double weight;
  bool operator<(const Edge& edge) const { return weight < edge.weight; }
};

const int MAX = 201;
int n, cnt;
int p[MAX], rank[MAX];
Edge edge[MAX * MAX];
double x[MAX], y[MAX];

void Init() {
  for (int i = 0; i < n; i++) {
    p[i] = i;
    rank[i] = 0;
  }
}

void Link(int x, int y) {
  if (rank[x] < rank[y])
    p[x] = y;
  else {
    p[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
  }
}

int Find(int x) {
  if (p[x] != x) p[x] = Find(p[x]);
  return p[x];
}

void Union(int x, int y) { Link(Find(x), Find(y)); }

double Kruskal() {
  sort(edge, edge + cnt);
  Init();
  for (int i = 0; i < cnt; i++) {
    if (Find(edge[i].from) != Find(edge[i].to)) Union(edge[i].from, edge[i].to);
    if (Find(0) == Find(1)) {
      return edge[i].weight;
    }
  }
  return 0.0;
}

int main() {
  double ret;
  int cas = 1;
  while (scanf("%d", &n), n) {
    for (int i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);
    cnt = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++) {
        edge[cnt].from = i;
        edge[cnt].to = j;
        edge[cnt].weight =
            sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
        cnt++;
      }
    ret = Kruskal();
    printf("Scenario #%d\n", cas++);
    printf("Frog Distance = %.3f\n\n", ret);
  }
  return 0;
}