TOI12: Pipe

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

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N = 15000;

vector<tiii> edges;
int ds[N + 1], sz[N + 1], dist[N + 1], par[N + 1];
pii coor[N + 1];

int distance(pii &a, pii &b){
    int dx = a.first - b.first;
    int dy = a.second - b.second;
    return abs(dx) + abs(dy);
}

int dsFind(int u){
    if(ds[u] == u){
        return u;
    }
    return ds[u] = dsFind(ds[u]);
}

int main(){

    int nVertex, tr;
    scanf("%d%d", &nVertex, &tr);
    for(int i = 1; i <= nVertex; ++i){
        scanf("%d%d", &coor[i].first, &coor[i].second);
    }

    // Prim Algorithm
    for(int i = 1; i <= nVertex; ++i){
        ds[i] = i;
        dist[i] = 1e9;
    }
    dist[1] = 0;
    par[1] = 1;
    for(int i = 0; i < nVertex; ++i){
        int mnDist = 1e9;
        int u = 0;
        for(int j = 1; j <= nVertex - i; ++j){
            if(dist[j] < mnDist){
                mnDist = dist[j];
                u = j;
            }
        }
        edges.emplace_back(dist[u], ds[u], par[u]);
        for(int v = 1; v <= nVertex - i; ++v){
            if(u == v){
                continue;
            }
            int w = distance(coor[ds[u]], coor[ds[v]]);
            if(w < dist[v]){
                dist[v] = w;
                par[v] = ds[u];
            }
        }
        swap(ds[u], ds[nVertex - i]);
        swap(dist[u], dist[nVertex - i]);
        swap(par[u], par[nVertex - i]);
    }

    // Kruskal Algorithm
    sort(edges.begin(), edges.end());
    for(int i = 1; i <= nVertex; ++i){
        ds[i] = i;
        sz[i] = 1;
    }
    int sum = 0;
    int compCnt = nVertex;
    for(tiii e : edges){
        int w = get<0>(e);
        int u = get<1>(e);
        int v = get<2>(e);
        u = dsFind(u);
        v = dsFind(v);
        if(u != v){
            sum += w;
            if(sz[u] < sz[v]){
                swap(u, v);
            }
            ds[v] = u;
            sz[u] += sz[v];
            --compCnt;
            if(compCnt == tr){
                cout << sum;
                return 0;
            }
        }
    }

    return 0;
}