洛谷P4047《[JSOI2010]部落划分》

二月 14, 2019 3341

最小生成树后删边

题目描述

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。

不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：

对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。

例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

输入输出格式

输入格式

输入文件第一行包含两个整数N和K(1<=N<=1000,1<K<=N)，分别代表了野人居住点的数量和部落的数量。

接下来N行，每行包含两个正整数x,y，描述了一个居住点的坐标(0<=x, y<=10000)。

输出格式

输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

输入输出样例

输入样例#1

1
2
3
4
5
4 2
0 0
0 1
1 1
1 0

输出样例#1

1
1.00

输入样例#2

1
2
3
4
5
6
7
8
9
10
9 3
2 2
2 3
3 2
3 3
3 5
3 6
4 6
6 2
6 3

输出样例#2

1
2.00

解题思路

我们首先对这几个点构建一个完全图

边数的计算属于初中数学内容（ \frac{n(n-1)}{2} ）

然后对这个图跑一遍最小生成树

删去生成树中最大的 k-1 条边，这时候整个图就变成了 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 1000 + 10;
const int MAXM = (MAXN * (MAXN - 1)) / 2 + 10;

struct Node {
    int x, y;
    
    Node() { x = y = 0; }
} node[MAXN];

struct Edge {
    int prev;
    int next;
    double weight;
    
    Edge() { prev = next = 0; weight = 0; }
    bool operator < (const Edge &that) const {
        return weight < that.weight;
    }
} edge[MAXM];

struct UnionFind {
    int seq[MAXN];
    
    UnionFind() { memset(seq, 0, sizeof seq); }
    int Find(int x) { return !seq[x] ? x : (seq[x] = Find(seq[x])); }
    bool Union(int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return false;
        seq[x] = y;
        return true;
    }
} U;

int n, k, cnt;

double GetPath(Node x, Node y) {
    double ret = 0;
    int X = std::abs(x.x - y.x);
    int Y = std::abs(x.y - y.y);
    ret = sqrt(X * X + Y * Y);
    // 勾股定理，初中数学
    return ret;
}

void Solve() {
    std::sort(edge + 1, edge + 1 + cnt);
    int tot = 0;
    for (int i = 1; i <= cnt; ++i) {
        bool routput = false;
        if (tot == n - k) routput = true;
        // 这里用了一个小技巧，加到 (n - k + 1) 条边的时候就可以输出，
        // 而不用到最后删边，因为边权是经过排序的
        if (U.Union(edge[i].prev, edge[i].next)) {
            ++tot;
            if (routput) {
                cout << std::fixed << std::setprecision(2) << edge[i].weight << endl;
                return;
            }
        }
    }
}

int main() {
    IMPROVE_IO();
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> node[i].x >> node[i].y;
    }
    // 构造完全图
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            edge[++cnt].prev = i;
            edge[cnt].next = j;
            edge[cnt].weight = GetPath(node[i], node[j]);
        }
    }
    Solve();
    return 0;
}