BZOJ 1821 [JSOI2010]Group 部落劃分（kruskal）

解法：一開始沒想到怎麼寫，但是慢慢覺得，同一個部落裡面的距離都是盡量短的，然後就像題目中的圖一樣兩個部落之間的距離就會很長，這個長度其實是由這個部落裡面某個人連出去和另一個部落的某個人的距離。我們直接跑一遍最小生成樹就好了，這樣自己部落的人的距離就是盡量短，然後這個生成樹最長的幾條邊裡面，直接輸出倒數第k-1條即可。

代碼如下：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<stack>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
int n, k, ppp;
pii p[maxn];
vector<double>len;

struct Node {
    int u, v;
    double c;
    bool operator < (const Node& tmp) const {
        if(c < tmp.c)
            return 1;
        return 0;
    }
}edge[maxm];

int par[maxn];
int Find(int x) {
    int root, tmp = x;
    while(x != par[x])
        x = par[x];
    root = x;
    x = tmp;
    while(x != par[x]) {
        tmp = par[x];
        par[x] = root;
        x = tmp;
    }
    return root;
}

void Union(int x, int y) {
    par[y] = x;
}

void kruskal() {
    for(int i = 0; i < ppp; i++) {
        int x = Find(edge[i].u);
        int y = Find(edge[i].v);
        if(x != y) {
            Union(x, y);
            len.push_back(edge[i].c);
        }
    }
}

double Count(int i, int j) {
    int x1 = p[i].first, x2 = p[j].first;
    int y1 = p[i].second, y2 = p[j].second;
    return sqrt(1.0 * (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("D:\\in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    scanf("%d%d", &n, &k);
    for(int i = 1, x, y; i <= n; i++) {
        scanf("%d%d", &x, &y);
        p[i].first = x;
        p[i].second = y;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            double d = Count(i, j);
            edge[ppp].u = i;
            edge[ppp].v = j;
            edge[ppp].c = d;
            ppp++;
        }
    }
    sort(edge, edge + ppp);
    for(int j = 1; j < maxn; j++)
        par[j] = j;
    kruskal();
    printf("%.2f\n", len[len.size() - k + 1]);
	return 0;
}