洛谷 P2498 [SDOI2012]拯救小云公主 题解【最短路】【贪心】【构造】【生成树】

点击量：196

   这种题是用SPFA优化的？？

目录

题目描述

英雄又即将踏上拯救公主的道路……

 

这次的拯救目标是——爱和正义的小云公主。

 

英雄来到boss的洞穴门口，他一下子就懵了，因为面前不只是一只boss，而是上千只boss。当英雄意识到自己还是等级1的时候，他明白这就是一个不可能完成的任务。

 

但他不死心，他在想，能不能避开boss去拯救公主呢，嘻嘻。

 

Boss的洞穴可以看成一个矩形，英雄在左下角（1,1），公主在右上角（row，line）。英雄为了避开boss，当然是离boss距离越远越好了，所以英雄决定找一条路径使到距离boss的最短距离最远。

 

Ps:英雄走的方向是任意的。

 

你可以帮帮他吗？

 

当英雄找到了美丽漂亮的小云公主，立刻就被boss包围了！！！英雄缓闭双眼，举手轻挥，白光一闪后使用了回城卷轴，回到了城堡，但只有小云公主回去了……因为英雄忘了进入回城的法阵了。

 

输入输出格式

输入格式：

第一行，输入三个整数，n表示boss的数目，row，line表示矩形的大小；

 

接下来n行，每行分别两个整数表示boss的位置坐标。

 

输出格式：

输出一个小数，表示英雄的路径离boss的最远距离，精确到小数点后两位。

 

输入输出样例

输入样例#1：

1 3 3

2 2

输出样例#1：

1.00

输入样例#2：

1 3 3

3 1

输出样例#2：

2.00

说明

数据范围：

20%数据，boss坐标范围小于等于50；

 

60%数据，n<=1500；

 

100%数据，n<=3000；

题解：

   首先想到的这个题做法肯定是二分答案+并查集，很像海滩防御，不过二分答案+并查集时间复杂度为$ O(n^2\alpha (n)\log n)$的，对于$ n=3000$的题就没有办法了。

   建立模型是在一个坐标系中，找出一个经过的最近两点间距离最长的方案，并输出最近两点的距离的一半。那么就是这种情况：

   红色箭头中最短的一条决定了这个题的答案，但是我们要使得这个最短的红色箭头的长度尽可能大。那么我们就可以不管其它红色箭头，只需要求一条尽可能长的。

   当问题出现限制时，它才好被解决，限制线可以把$ (1,1)$和$ (x,y)$分为两个部分，换一种思路理解就是把矩形的左侧/上侧与矩形的右侧/下侧连接了起来。如果限制线是这样的：

   那么每条限制线中最长的一段就是上面的红色箭头，我们只要在每段限制线中取最长的，然后再取这些最长的中最短的，就是想要的答案了。生成限制线可以用最小生成树做。

为什么呢？

   考虑Kruskal，Kruskal是依次检验每条边两点是否在同一集合上，这样当并查集使得左上和右下相连时，最后一根连上的边促成了一根完整的限制线，此时这根限制线是图中限制最严格的线，其他线都还有更宽松的还没有被限制的路可以走。也就是可以任意走红色线段以外，且比当前最严格线更宽松的其他线段，那么当前最严格线就是上文所述每条限制线最长的边集合中最短的一条。

   但是如果图中的限制线不是这样有层次的，而是层次之间互相缠绕，那也没有关系，因为我们只关心第一条将左上和右下相连的限制线及其最长的边。

但是…

   碍于3000的数据，对于$ E\log E \ E=9\times 10^6$，Kruskal是不可行的，只能用prim。prim的正确性证明：它所找的是当前不完全生成树的最小外来边，一旦左上和右下同属这棵树，生成树中最大的边就是当前解。如果当前不是最优，那么更优的链一定在当前链之前被更新进树中。因为它是最小生成树，所以树的任意两点间路径上最大权值保证了最小。（此条性质参见NOIp2013提高组 货车运输）

   这样一来，我们的目的就是求一条左上代表的点到右下代表的点的路径，满足这条路径的最长边最短。这条最长边就是所求答案，因此可以用SPFA松弛到当前点的最短的路径最长边来做。

如何连边？

   如果英雄从两个boss之间(之间没有其他boss)走，那么一定当且仅当经过它们的中点时最优，把这两个点之间连一条长为$ \frac{\sqrt{(x_1-x_2)^2(y_1-y_2)^2}}2$的边。如果英雄从一个boss和边界走，那么他一定要贴墙走。此时连边权为到两边界中较近那一个的距离的边，因为我们要保证最长边最短。

Code of SPFA：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using std::queue;
double f[3100][3100];
struct pnt
{
    double x,y;
    pnt(double x,double y)
    {
        this->x=x;
        this->y=y;
    }
    pnt(){}
    friend bool operator <(pnt a,pnt b)
    {
        if(a.x!=b.x)
            return a.x>b.x;
        return a.y<b.y;
    }
}p[3100];
bool cmp(pnt a,pnt b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y>b.y;
}
int n;
double spfa()
{
    queue<int> q;
    double dis[3100];
    bool used[3100];
    for(int i=1;i<=n+1;i++)
        dis[i]=99999999.0;
    memset(used,0,sizeof(used));
    used[0]=true;
    dis[0]=0;
    q.push(0);
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        used[k]=false;
        for(int i=1;i<=n+1;i++)
            if(std::max(dis[k],f[k][i])<dis[i])
            {
                dis[i]=std::max(dis[k],f[k][i]);
                if(!used[i])
                {
                    used[i]=true;
                    q.push(i);
                }
            }
    }
    return dis[n+1];
}
int main()
{
    double x,y;
    scanf("%d%lf%lf",&n,&x,&y);
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=n+1;j++)
            f[i][j]=99999999;
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=1;i<=n;i++)
        f[0][i]=f[i][0]=std::min(x-p[i].x,p[i].y-1);

    for(int i=1;i<=n;i++)
            f[n+1][i]=f[i][n+1]=std::min(y-p[i].y,p[i].x-1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            f[i][j]=f[j][i]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/2;
    printf("%.2lf\n",spfa());
    return 0;
}