CF33D Knights 题解

· · 题解

题目描述

你是一位OIer，今天教练刚讲了LCA，你看到了CF33D Knights，打算做一下它。

你简化了问题：给你几个点的坐标和几个圆的坐标与半径（任意两个圆都没有交叉点），求一个点到另一个点最少经过几个圆。

思路

你想到了一个做法：如果圆 A 包含圆 B ，且A 是包含圆 B 的圆中半径最小的，则将 A 、 B 连边，容易证得得到的是一个森林，而最外层的圆自然地连接到了虚根0号结点。然后我们计算出每一个点属于哪一个圆（这里的属于定义为：圆 A 包含点 B ，且圆 A 是包含点 B 的圆中半径最小的），查询的时候就通过 LCA 和树的深度求得点所属圆在树上的最短距离。

代码处理

但是第一个问题出现了：如何判断圆 A 是包含圆 B 的圆中半径最小的？

你想了想，处理方案如下：

1.先将所有圆以半径为关键字升序排序；

2.以下标为序搜索每一个圆，代码如下：

void df(int q)//搜索第q个圆//不要在意变量名
{
    if(v[q])return;//如果被搜索过了则return
    v[q]=1;//标记
    for(int i=1;i<=m;i++)//循环每一个圆
    {
        if(check(q,i)&&i!=q)//check(q,j)的意思是圆q能被圆i包含，下同
        {//如果圆q被圆i包含且i不等于q
            adde(q,i);
            adde(i,q);//加边
            df(i);//搜索地i个圆
            return;
        }
    }
}//这样就可以保证圆i是包含圆q的圆中半径最小的

第二个问题：怎么找到最外层的圆？

下面是处理方式+代码（不好叙述，具体讲解在代码中）：

for(int i=1;i<=m;i++)//循环每一个圆
   {
    bool p=1;
    for(int j=i+1;j<=m;j++)
    {
        if(check(i,j))p=0;//如果i能被其他圆包含，则一定不是最外层的圆
    }
    if(p)adde(i,0),adde(0,i);//加边
}

你的一个朋友发表不同的意见：”其实可以加一个无限大的圆使其它圆被它包含“。

第三个问题：如何确定点属于哪一个圆？

处理方式+代码（不好叙述，具体讲解在代码中）：

for(int i=1;i<=m;i++)//循环圆
{
    for(int j=1;j<=n;j++)//循环点
    {
        if(!z[j]&&(判断点是否在圆内)/*代码很长且可读性较差，故不展示*/)z[j]=i;//建立关系
    }//因为圆是按半径排列的，所以如果圆i包含了点j，则圆i+1一定包含点j
}    //所以要判断点j是否已经建立关系，防止重复建立关系
for(int i=1;i<=n;i++)if(!z[i])z[i]=0;
//如果没有圆与这个点建立关系就代表这个点与虚根相连
//或者说这个点属于最外面的无限大的圆

主函数代码实现

int main()
{
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;i++)scanf("%d%d",&mp[i][1],&mp[i][2]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&O[i].r,&O[i].x,&O[i].y);//输入
    sort(O+1,O+m+1,cmp);//排序
    for(int i=1;i<=m;i++)
    {
        if(!v[i])df(i);
    }//问题一
    for(int i=1;i<=m;i++)
    {
        bool p=1;
        for(int j=i+1;j<=m;j++)
        {
            if(check(i,j))p=0;
        }
        if(p)adde(i,0),adde(0,i);
    }//问题二
    dfs(0,0);//LCA基本操作
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
              if(!z[j]&&(long long)((long long)(O[i].x-mp[j][1])*(O[i].x-mp[j][1])+(long long)(O[i].y-mp[j][2])*(O[i].y-mp[j][2]))<=(long long)O[i].r*O[i].r)z[j]=i;
        }
    }
    for(int i=1;i<=n;i++)if(!z[i])z[i]=0;//问题三
    while(T--)
    {
        int q,w;
        scanf("%d%d",&q,&w);
        printf("%d\n",d[z[w]]+d[z[q]]-2*d[LCA(z[q],z[w])]);
        //找到最少次数并输出
    }
}

完整代码