题解：P8191 [USACO22FEB] Moo Network G

· · 题解

首先考虑到暴力建边加上最小生成树，这个显然超时，预期通过 N \le 1000 的数据。

考虑优化。同时可以发现题目的限制 0\le y \le 10，我们可以考虑如何少建一些边。

我们可以把所有点分层（在平面直角坐标系中以纵坐标分层）。对于同一层的点，显然地，相邻的点连一条边。对于不同层的点，按照横坐标排序，相邻的点同样连一条边。

连边之后就是最小生成树。

:::success[代码]

#include<bits/stdc++.h>
#define N 100005
#define M 5000005
using namespace std;
typedef long long ll;

struct edge{ll u,v,w;bool operator < (const edge &k)const{return w<k.w;}};
int n,x[N],y[N],fa[N],cnt;
vector<int> st[N];
edge g[M];
int find(int k){return fa[k]==k?k:fa[k]=find(fa[k]);}

bool cmp(int a,int b)
{
    return x[a]<x[b];
}

ll dis(int u,int v)
{
    return (1LL*x[u]-x[v])*(1LL*x[u]-x[v])+(1LL*y[u]-y[v])*(1LL*y[u]-y[v]);
}

int main()
{
//  freopen("sample.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i],st[y[i]].push_back(i);
    for(int i=0;i<=10;i++)stable_sort(st[i].begin(),st[i].end(),cmp);
    for(int i=0;i<=10;i++)
    {
        int len=st[i].size();
        for(int j=0;j<len-1;j++)
            g[++cnt]={st[i][j],st[i][j+1],dis(st[i][j],st[i][j+1])};
    }
    for(int i=0;i<=10;i++)
    {
        for(int j=i+1;j<=10;j++)
        {
            vector<int> now;
            for(auto k:st[i])now.push_back(k);
            for(auto k:st[j])now.push_back(k);
            stable_sort(now.begin(),now.end(),cmp);
            int len=now.size();
            for(int k=0;k<len-1;k++)
                g[++cnt]={now[k],now[k+1],dis(now[k],now[k+1])};
        }
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    stable_sort(g+1,g+cnt+1);
    ll ans=0;
    for(int i=1;i<=cnt;i++)
    {
        ll u=g[i].u,v=g[i].v,w=g[i].w;
        if(find(u)!=find(v))
        {
            fa[find(v)]=find(u);
            ans+=w;
        }
    }
    cout<<ans;
    return 0;
}

::: 最后注意 64 位整数记录开销。