Moo Network (USACO Gold 2022 February)

看起来是一个全连通图，但是不是所有的边都有用，我们只用生成出有用的边就可以解这个题。具体来说，因为 $y$ 的范围是 $[0,10]$ ，所以根据Kruskal的思想，每次都加最短的能把两个连通分量合并的边。

先考虑 $x$ 相邻的边，这些边就已经可以把所有节点加进来，只是不一定是最短的。所以我们只需要 $x$ 相邻的边，以及可能比这个更短的边就行了。

具体办法，就是对于每一个点，生成在 $[0,10]$ 这11个row上面的 $x$ 相邻的边就可以了，如果有比所有点中 $x$ 相邻的点更近的点，那一定会被这 $11$ 条边覆盖。复杂度是 $\mathcal{O}(n \log n)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
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;
}