信息学奥赛一本通T1437-扩散

解题思路: 二分+并查集

注意事项:

参考代码:

#include <iostream>

#include <algorithm>

using namespace std;

#define int long long

const int N=2e2;

int n;

struct node{

    int x,y;

}a[N];

int fa[N];

int dist[N][N];//记录两坐标间的曼哈顿距离

int find(int x)

{

    if(fa[x]==x)

        return x;

    else

        return fa[x]=find(fa[x]);

}

void Union(int x,int y)

{

    x=find(x);

    y=find(y);

    if(x!=y)

        fa[x]=y;

}

bool solve(int mid)

{

    for(int i=1;i<=n;i++)//初始化并查集

        fa[i]=i;

    for(int i=1;i<n;i++)

    {

        for(int j=i+1;j<=n;j++)

        {

            if(dist[i][j]<=mid*2)//两点间的距离能在mid内连通

                Union(i,j);

        }

    }

    int cnt=0;

    for(int i=1;i<=n;i++)

    {

        if(fa[i]==i)

            cnt++;

        if(cnt==2)//有2个以上就不符合

            return false;

    }

    return true;

}

signed main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i].x>>a[i].y;

    for(int i=1;i<n;i++)

    {

        for(int j=i+1;j<=n;j++)

        {

            dist[i][j]=dist[j][i]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);

            //两点的曼哈顿距离

        }

    }

    int l=0,r=1e9;

    while(l<r)//二分答案--时间

    {

        int mid=(l+r)/2;

        if(solve(mid))

            r=mid;

        else

            l=mid+1;

    }

    cout<<l;

    return 0;

}