「Bzoj 1821」「JSOI2010」部落划分 Group (最小生成树)

BZOJ 1821
平面上给点询问边权问题一般是最小生成树。
我们把点一一存边，然后最小生成树加边，加到有$k$个连通分量后，输出下一条能够使联通分量增加的边的边权即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5;
int en, n, k, f[MAXN];
struct pos {int x, y;}p[MAXN];
struct data {
    int u, v;
    db dist;
    bool operator < (const data &b) const {
        return dist < b.dist;
    }
}e[MAXN * MAXN];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
db getDist(pos &a, pos &b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void clean() {
    en = 0;
    for (int i=1;i<=n;i++) f[i] = i;
}
void solve() {
    clean();
    for (int i=1;i<=n;i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            en++;
            e[en].u = i, e[en].v = j, e[en].dist = getDist(p[i], p[j]);
        }
    }
    sort(e + 1, e + 1 + en);
    int tot = 0;
    for (int i=1;i<=en;i++) {
        int x = find(e[i].u), y = find(e[i].v);
        if (x == y) continue;
        f[x] = y;
        tot++;
        if (tot > n - k) {printf("%.2f\n", e[i].dist); return ;}
    }
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &k), solve();
    return 0;
}