kruskai，贪心

题意：

分析：

这一题我是由kruskai算法为突破口的。
我们想想，对于一揽子的节点，我们要对他们进行并查集操作，将其合成k个集合。
然后求集合间的最短距离。我们想 让这个最短距离尽量大！

由kruskai算法作为突破口，我们不妨对所有的边按照其权值从小到大排序。
边：共有n*n-n个，权值为距离。
然后贪心的从距离最小的边开始进行合并，直到合成k个集合。也就是执行kruskai算法操作。
最后，遍历剩下的边，找到最小距离。

为什么可以这样贪心呢？
因为，我们最终是要形成k个集合的对吧。那么我们为什么不尽量用距离小的边去形成k个集合呢？
如果我们对于一个距离为1的边放着不用，去用一个距离为2的边的话，距离为1的边就有可能成最短边了！

贪心是成立的。
kruskai算法！！！

代码如下，我直接使用我的kruskai算法板子了

#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
const int max_n = 1100;
int n, k;
vector<pii> points;
struct edge
{
    int u, v, next;
    ll cost;
}E[max_n * max_n];
int head[max_n];
int cnt = 1;
void add(int from, int to,ll cost) {
    E[cnt].u = from;
    E[cnt].v = to;
    E[cnt].cost = cost;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

int par[max_n];
int rak[max_n];
void init() {
    points.clear();
    fill(head, head + 1 + n, false);
    fill(rak, rak + 1 + n, 0);cnt = 1;
    for (int i = 0;i <= n;i++)par[i] = i;
    k = n - k;
}
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int u, int v) {
    u = find(u);v = find(v);
    if (u == v)return false;
    if (rak[u] > rak[v])par[v] = u;
    else if (rak[v] > rak[u])par[u] = v;
    else par[v] = u, rak[u]++;
    return true;
}

bool cmp(edge& e1, edge& e2) { return e1.cost < e2.cost; }
double kruskai() {
    int i;
    sort(E + 1, E + 1 + cnt-1, cmp);
    for (i = 1;i <= cnt-1 && k;i++) {
        int u = E[i].u;int v = E[i].v;
        if (merge(u, v))
            k--;
    }
    for (;i <= cnt - 1;i++)
        if (!same(E[i].u, E[i].v))
            return sqrt(E[i].cost);
    return 0;
}

ll compute(ll x1, ll y1, ll x2, ll y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> k;init();
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;
        points.push_back({ x,y });
    }for (int i = 0;i < n;i++) {
        int x1 = points[i].first;
        int y1 = points[i].second;
        for (int j = i + 1;j < n;j++) {
            int x2 = points[j].first;
            int y2 = points[j].second;
            ll cost = compute(x1, y1, x2, y2);
            add(i + 1, j + 1, cost);add(j + 1, i + 1, cost);
        }
    }
    cout << fixed << setprecision(2) << kruskai() << endl;
}