题解 P4675 【[BalticOI 2016 day1]Park】

· · 题解

做题目时因为没有题解，自己调试了半天，于是想把自己的程序分享一下，给后来者参考参考。

进入正题

这道题目运用到了\color{#ff0481}\boxed{\small\texttt{并查集}}、\color{#ff0481}\boxed{\small\texttt{离线}}。
上述算法不清楚不要紧，我们慢慢来。

并查集

并查集从字面意思上来理解，是一种支持合并与查询的数据结构。并查集的合并指的是将两颗有根树合并，查询指的是查询节点的根。

并查集的基本思路是路径压缩，对于任意节点x，我们让节点x的父指针指向根，根的父指针指向自己，这样查询时便可以一步到位。对于合并，就只需查找根节点，然后将其中一个根的父指针指向另一个根就行了。但是，你可能有疑惑，这样并没有路径压缩呀。其实，路径压缩是在查询时进行的。我们一边查询一边用返回值更新父指针，如代码：

inline int find(int x)                    //查询根节点
{
    if (f[x]==x) return x;                //如果当前节点为根节点，返回本身。
    f[x]=find(f[x]);                      //否则，查询父节点，并将父指针指向根节点。
    return f[x];                          //返回根节点
}

合并的代码就更加简单了：

inline void together(int x,int y)
{
    int r1,r2;
    r1=find(x);r2=find(y);       //查询x、y的根
    if (r1==r2) return ;         //若x、y以在同一棵树中，不合并
    f[r1]=r2;                    //将r1的根置为r2
}

这一题，我们可以用并查集来判断连通情况，如果树与边界相交或树与树相交(相切也算)，合并。最后，判断两边界是否处于同一集合中，若是，则不能通行，否则，能过。但这也仅仅只是判断了相交的情况，一些情况下，即使是两树不相交，它们的距离过小，长得胖的人也过不去。

对与这个情况，一种解决方法是建立m个并查集，枚举距离，小于人的直径时，就合并。当这种方法时间复杂度太高。于是，我便想到了第二种方法，离线处理，将人按直径(输入是半径)由小到大排序，距离也按由小到大排序，这样原先无法通过的距离，之后任然无法通过。就不需要重复处理，还可以用一个last变量记录上次判断到的距离。

code:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=2015;
const int MAXM=100015;
const double eps=1e-4;
int n,m,id,last,k;
long long l,r;

struct tree
{
    long long x,y,d;

    inline double operator - (struct tree tmp) 
    {
        return sqrt((x-tmp.x)*(x-tmp.x)+(y-tmp.y)*(y-tmp.y))-d-tmp.d;
    }
}t[MAXN];

struct man
{
    long long from,id,d;

    inline bool operator < (const man &tmp) const
    {
        return d<tmp.d;
    }
}w[MAXM];

struct cost
{
    long long a,b;double dis;

    inline bool operator < (const cost &tmp) const
    {
        return dis<tmp.dis;
    }
}h[MAXN*MAXN];
int f[MAXM];
bool ans[MAXM][5],map[5][5];

inline int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}

inline void together(int x,int y)
{
    int r1,r2;
    r1=find(x);r2=find(y);
    if (r1==r2) return ;
    f[r1]=r2;
}

inline void turn_off(int x,int y)
{
    map[x][y]=map[y][x]=false;
}

int main()
{
    cin>>n>>m>>l>>r;
    for (int i=1;i<=n;i++) cin>>t[i].x>>t[i].y>>t[i].d;
    for (int i=1;i<=m;i++) {cin>>w[i].d>>w[i].from;w[i].d*=2;w[i].id=i;}
    for (int i=1;i<=n;i++)
    {
        h[++id]=(cost){i,n+1,(double)t[i].x-t[i].d};
        h[++id]=(cost){i,n+2,(double)t[i].y-t[i].d};
        h[++id]=(cost){i,n+3,(double)l-t[i].x-t[i].d};
        h[++id]=(cost){i,n+4,(double)r-t[i].y-t[i].d};
        for (int j=i+1;j<=n;j++) h[++id]={i,j,fabs(t[i]-t[j])};
    }
    last=1;
    sort(h+1,h+id+1); sort(w+1,w+m+1);
    for (int i=1;i<=4;i++)
        for (int j=1;j<=4;j++) map[i][j]=true;
    for (int i=1;i<=n+10;i++) f[i]=i;
    for (int i=1;i<=m;i++)
    {
        while (last<=id&&h[last].dis+eps<=w[i].d) {together(h[last].a,h[last].b);last++;}
        if (find(n+1)==find(n+3)) turn_off(1,3),turn_off(1,4),turn_off(2,3),turn_off(2,4);
        if (find(n+2)==find(n+4)) turn_off(1,2),turn_off(1,3),turn_off(2,4),turn_off(3,4);
        if (find(n+1)==find(n+2)) turn_off(1,2),turn_off(1,3),turn_off(1,4);
        if (find(n+2)==find(n+3)) turn_off(1,2),turn_off(2,4),turn_off(2,3);
        if (find(n+3)==find(n+4)) turn_off(3,1),turn_off(3,2),turn_off(3,4);
        if (find(n+4)==find(n+1)) turn_off(4,1),turn_off(4,2),turn_off(4,3);
        for (int j=1;j<=4;j++) ans[w[i].id][j]=map[w[i].from][j];
    }
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=4;j++)
            if (ans[i][j]) putchar(j+'0');
        putchar('\n');
    }
    return 0;
}
Please~give~a~like.~~Thanks~for~reading~my~passage.