洛谷P7991题解

Ginger_he · 2022-01-03 17:52:52 · 题解

题解

并查集+二分查找好题
由于至多连两条边，所以只有三种情况。
若不连边，则 1 和 n 连通；
若连一条边，则在分别在 1 和 n 所在的连通块里找一个点连边；
若连两条边，则找一个点分别与 1 和 n 所在的连通块里找一个点连边。
这三种情况的最小值就是答案，时间复杂度 \Theta(n\log n)。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int t,n,m,u,v,fa[maxn];
ll ans;
vector<int> g[maxn];
ll square(int x)
{
    return (ll)x*x;
}
int find(int x)
{
    if(x==fa[x])
        return x;
    return fa[x]=find(fa[x]);
} 
ll dis(int x,int y)
{
    ll res=1e18;
    int a,b;
    for(int i=0;i<g[x].size();i++)
    {
        a=g[x][i],b=lower_bound(g[y].begin(),g[y].end(),a)-g[y].begin();//二分
        if(b) res=min(res,square(a-g[y][b-1]));//比a小里最接近a的 
        if(b<g[y].size()) res=min(res,square(a-g[y][b]));//比a大里最接近a的 
    }
    return res;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            g[i].clear();
        }//初始化 
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            fa[find(u)]=find(v);
        }
        for(int i=1;i<=n;i++)
            g[find(i)].push_back(i);
        u=fa[1],v=fa[n],ans=dis(u,v);//1与n直接相连 
        for(int i=1;i<=n;i++)
        {
            if(fa[i]==u||fa[i]==v||fa[i]!=i)
                continue;
            ans=min(ans,dis(i,u)+dis(i,v));//找到某个点与1和n相连 
        }
        printf("%lld\n",ans);
    }
    return 0;
}