import {Title, Resources, ResourceItem, QList, Q, Focus} from "@/lib/noip"

Moo Network

  1. 看起来是一个全连通图，但是不是所有的边都有用，我们只用生成出有用的边就可以解这个题。
  2. 具体来说，因为yy的范围是[0,10][0,10]，所以根据Kruskal的思想，每次都加最短的能把两个连通分量合并的边。
  3. 先考虑xx相邻的边，这些边就已经可以把所有节点加进来，只是不一定是最短的。所以我们只需要xx相邻的边，以及可能比这个更短的边就行了。
  4. 具体办法，就是对于每一个点，生成在[0,10][0,10]这11个row上面的xx相邻的边就可以了，如果有比所有点中xx相邻的点更近的点，那一定会被这11条边覆盖。
  5. 复杂度是O(nlog⁡n)\mathcal{O}(n\log{n})，再乘以一个11是常数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// n <= 1e5
int n;
pair<int,int> cs[100005];       // x,y, 0 <= x <= 1e6, 0 <= y <= 10
vector<pair<int,int>> rs[11];              // all (x,idx) values for each y
struct E {
    int u,v;
    ll d;
};
vector<E> es;
bool cmp(E &a, E &b) {return a.d < b.d;}
int fa[100005];
 
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
 
bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y) {
        fa[x] = y;
        return true;
    } else 
        return false;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
        scanf("%d %d", &cs[i].first, &cs[i].second);
    sort(cs,cs+n);
    for (int i = 0; i < n; i++)
        rs[cs[i].second].push_back({cs[i].first,i});
    int nxt[11] = {0};  // pointer to next value in the same row
    for (int i = 0; i < n; i++) {
        int x = cs[i].first, y = cs[i].second;
        assert(rs[y][nxt[y]].first == x);
        nxt[y]++;
        for (int j = 0; j <= 10; j++) {
            if (nxt[j] < rs[j].size()) {
                // add an edge
                int x2 = rs[j][nxt[j]].first;
                es.push_back({i,rs[j][nxt[j]].second,(ll)(x-x2)*(x-x2)+(ll)(y-j)*(y-j)});
            }
        }
    }
    sort(es.begin(), es.end(), cmp);
 
    // Kruskals
    ll ans = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        fa[i]=i;
    for (E e: es) {
        if (merge(e.u, e.v)) {
            ans += e.d;
            if (++cnt == n-1) break;
        }
    }
    printf("%lld", ans);
 
    return 0;
}