题解 P2632 【Explorer】

· · 题解

题意：

给出两条直线，上面分别有 n,m 个点，求其最小生成树。

观察发现，一个点在最小生成树中可能连接的点只可能有 4 个：自己这条直线上相邻的两个点；向另一条直线做垂线得到的垂足旁边的两个点（下图中 B 对应可以选择连接 A_1,A_2，不可能连接 BA_3）。

不能跨过自己直线上相邻的点非常显然：

既然连接了 A_1A_3 为什么不用相同的代价连接 A_1A_2,A_2A_3。

对于连接另一条直线上的点的情况：

假设在一个生成树中 B 连接到了 A_3，对删除 A_2,A_3,B 之间的边之后的连通情况进行分类讨论：

若 B 与 A_2 在同一连通块内，则连接 A2A3 更优。

若 A_2 与 A_3 在同一连通块内，则连接 BA_2 更优。

若三点均在不同连通块内，则连接 BA_2,A_2A_3 更优。

故所有连接了 BA_3 的生成树都不是最小生成树。

然后按照限制加边跑最小生成树即可。

代码（实际上这个代码多连了 25\% 的无效边，但不影响正确性，O((n+m)log(n+m))）：

#include<bits/stdc++.h>
using namespace std;
struct node{double x,y;}a[100001],b[100001];
struct e{int u,v;double d;}c[2000001];
inline bool cmp1(node i,node j){return i.x<j.x;}
inline bool cmp2(e i,e j){return i.d<j.d;}
int n,m,cnt,fa[200001];
double ax,ay,bx,by,cx,cy,dx,dy,t,ans;
int find(int i){return fa[i]==i?i:fa[i]=find(fa[i]);}
double dis(node i,node j){return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);}
int main()
{
    scanf("%d%d%lf%lf%lf%lf%lf%lf%lf%lf",&n,&m,&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
    for(int i=1;i<=n;i++)scanf("%lf",&t),a[i]={ax*t+bx*(1-t),ay*t+by*(1-t)},fa[i]=i;
    for(int i=1;i<=m;i++)scanf("%lf",&t),b[i]={cx*t+dx*(1-t),cy*t+dy*(1-t)},fa[n+i]=n+i;
    sort(a+1,a+n+1,cmp1),sort(b+1,b+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
        int l=1,r=m,midl,midr,ok=0;
        while(l<r-5)
        {
            midl=(l*2+r)/3,midr=(l+r*2)/3;
            if(dis(a[i],b[midl])<dis(a[i],b[midr]))r=midr;
            else l=midl;
        }
        for(int j=l;j<r;j++)if(dis(b[i],a[j])<dis(b[i],a[j+1]))
        {
            if(j!=1)c[++cnt]={i,n+j-1,dis(a[i],b[j-1])};
            c[++cnt]={i,n+j,dis(a[i],b[j])},c[++cnt]={i,n+j+1,dis(a[i],b[j+1])};
            ok=1;
            break;
        }
        if(!ok)
        {
            if(r!=1)c[++cnt]={i,n+r-1,dis(a[i],b[r-1])};
            c[++cnt]={i,n+r,dis(b[i],a[r])};
            if(r!=m)c[++cnt]={i,n+r+1,dis(a[i],b[r+1])};
        }
    }
    for(int i=1;i<=m;i++)
    {
        int l=1,r=n,midl,midr,ok=0;
        while(l<r-5)
        {
            midl=(l*2+r)/3,midr=(l+r*2)/3;
            if(dis(b[i],a[midl])<dis(b[i],a[midr]))r=midr;
            else l=midl;
        }
        for(int j=l;j<r;j++)if(dis(b[i],a[j])<dis(b[i],a[j+1]))
        {
            if(j!=1)c[++cnt]={n+i,j-1,dis(b[i],a[j-1])};
            c[++cnt]={n+i,j,dis(b[i],a[j])},c[++cnt]={n+i,j+1,dis(b[i],a[j+1])};
            ok=1;
            break;
        }
        if(!ok)
        {
            if(r!=1)c[++cnt]={n+i,r-1,dis(b[i],a[r-1])};
            c[++cnt]={n+i,r,dis(b[i],a[r])};
            if(r!=m)c[++cnt]={n+i,r+1,dis(b[i],a[r+1])};
        }
    }
    for(int i=1;i<n;i++)c[++cnt]={i,i+1,dis(a[i],a[i+1])};
    for(int j=1;j<m;j++)c[++cnt]={n+j,n+j+1,dis(b[j],b[j+1])};
    sort(c+1,c+cnt+1,cmp2);
    for(int i=1;i<=cnt;i++)if(find(c[i].u)!=find(c[i].v))fa[fa[c[i].u]]=fa[c[i].v],ans+=sqrt(c[i].d);
    printf("%.3lf",ans);
    return 0;
}