[JSOI2010] 部落划分

GitHub跳转原题关系图返回列表

把居住点建成完全图，按距离做 Kruskal 聚类，剩 k 个集合时的下一条跨集合边就是答案。

OJ: luogu

题目 ID: P4047

难度:普及+/提高

标签:最小生成树Kruskal并查集几何贪心

日期: 2026-01-03 10:27

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定平面上的 n 个居住点，要把它们划分成 k 个部落。

两个部落之间的距离，定义为两个部落中最近一对点的距离。要求最大化“最近的两个部落之间的距离”，输出这个最大值。

思路

先看一个可以直接验证想法的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：枚举小数据的 k 个部落划分，用来辅助对拍。

const int MAXN = 12;

int n, k;
int x_pos[MAXN], y_pos[MAXN];
int group_id[MAXN];
double answer;

double dist_point(int i, int j) {
    double dx = x_pos[i] - x_pos[j];
    double dy = y_pos[i] - y_pos[j];
    return sqrt(dx * dx + dy * dy);
}

void read_input() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x_pos[i] >> y_pos[i];
    }
}

void evaluate() {
    double nearest = 1e100;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (group_id[i] != group_id[j]) {
                nearest = min(nearest, dist_point(i, j));
            }
        }
    }
    answer = max(answer, nearest);
}

void dfs(int pos, int used_groups) {
    if (pos == n + 1) {
        if (used_groups == k) {
            evaluate();
        }
        return;
    }

    for (int g = 1; g <= used_groups; g++) {
        group_id[pos] = g;
        dfs(pos + 1, used_groups);
    }

    if (used_groups < k) {
        group_id[pos] = used_groups + 1;
        dfs(pos + 1, used_groups + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    answer = 0.0;
    group_id[1] = 1;
    dfs(2, 1);

    cout << fixed << setprecision(2) << answer << '\n';

    return 0;
}

暴力枚举所有划分方法，可以直接检查定义，但划分数量太多，只能用于小数据对拍。

把每个居住点看作点，任意两个点之间连边，边权为欧氏距离。题目就变成：把完全图的点分成 k 个簇，使不同簇之间的最小边尽量大。

直觉上，距离越近的点越应该放在同一个部落里，否则答案会被这条短距离限制住。于是按距离从小到大做 Kruskal：

  1. 一开始每个点单独一个集合；
  2. 按距离从小到大枚举点对；
  3. 如果两点不在同一集合，并且当前集合数还大于 k，就合并；
  4. 当集合数已经等于 k 时，遇到的第一条跨集合边，就是最近的两个部落距离。

代码里用平方距离排序，避免比较浮点数。最终输出答案时再开平方并保留两位小数。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXE = 1000005;

struct Edge {
    int u, v;
    long long dist2;
};

int n, k;
int x_pos[MAXN], y_pos[MAXN];
Edge edge[MAXE];
int edge_count;
int father[MAXN];

bool cmp_edge(const Edge &a, const Edge &b) {
    return a.dist2 < b.dist2;
}

int find_root(int x) {
    if (father[x] == x) {
        return x;
    }
    father[x] = find_root(father[x]);
    return father[x];
}

bool merge_set(int x, int y) {
    int rx = find_root(x);
    int ry = find_root(y);
    if (rx == ry) {
        return false;
    }
    father[rx] = ry;
    return true;
}

long long square_dist(int i, int j) {
    long long dx = x_pos[i] - x_pos[j];
    long long dy = y_pos[i] - y_pos[j];
    return dx * dx + dy * dy;
}

void read_input() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x_pos[i] >> y_pos[i];
    }
}

void build_edges() {
    edge_count = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            edge_count++;
            edge[edge_count].u = i;
            edge[edge_count].v = j;
            edge[edge_count].dist2 = square_dist(i, j);
        }
    }
}

void solve() {
    build_edges();
    sort(edge + 1, edge + edge_count + 1, cmp_edge);

    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }

    int components = n;
    for (int i = 1; i <= edge_count; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        if (find_root(u) == find_root(v)) {
            continue;
        }

        if (components == k) {
            double answer = sqrt((double)edge[i].dist2);
            cout << fixed << setprecision(2) << answer << '\n';
            return;
        }

        merge_set(u, v);
        components--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

完全图有 O(n2)O(n^2) 条边，排序复杂度为 O(n2logn)O(n^2 log n)。

空间复杂度为 O(n2)O(n^2)。

总结

这道题本质是 Kruskal 聚类。

最小生成树不一定要完整建出来：当连通块数剩下 k 个时停止合并，下一条连接不同集合的边就是最优部落间距。