扩散-并查集-二分

妖狐艹你老母 2022-12-03 09:10 167阅读 0赞

n1#include <iostream>
    #include <cstdio>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    4
    32 19
    21 14
    44 2
    48 13
    */
    
    int n;
    struct node
    {
        
        int x,y;
    }a[55];
    
    int d[55][55];
    int fa[55];
    
    int juli(int i,int j)
    {
        
        return abs(a[i].x-a[j].x) + abs(a[i].y-a[j].y);
    }
    
    int find(int x)
    {
        
        //printf("%d",x);
        //printf("?");
        if(x==fa[x])
        {
        
            return x;
        }
        else
        {
        
            return fa[x]=find(fa[x]);
        }
    
    }
    bool check(int x)
    {
        
    	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(d[i][j]<=x*2)//同样的距离小于两倍的时间
    			{
        
    				int fx=find(i),fy=find(j);
    				//先找到自己共同的祖先，就是要相交的时候到达的点
    				if(fx!=fy)fa[fx]=fy;
    				//如果不一样的话，将其中一个与另一个变为一样的
    			}
    	int sum=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(fa[i]==i)sum++;//祖先相同的话，这样的走向就成立
    		if(sum==2)return false;
    		/*如果有两个祖先的话，说明最短距离没有找对，
    		因为只能允许一个最近的祖先*/
    	}
    	return true;
    }
    /*
    bool check(int t)
    {
        // 并查集
        // 初始化fa数组
        for(int i=0;i<n;++i)
        {
            fa[i]=i;
        }
        //printf("?");
    
        // 利用距离小于t时满足的条件，更新fa数组，合并并查集。
        int fi,fj;
        for(int i=0;i<n;++i)
        {
            for(int j=i+1;j<n;++j)
            {
                if(dis[i][j]<=t*2)
                {
                    fi=Find(i);
                    fj=Find(j);
                    if(fi!=fj)
                    {
                        fa[fi]=fj;
                    }
                }
                //printf("i:%d j:%d  ",i,j);
                //fi=Find(i);
                //fj=Find(j);
                //printf("fi:%d fj:%d\n",fi,fj);
    //            if(fi!=fj)
    //            {
    //                if()
    //                {
    //                    //printf("manzu  ");
    //                    //printf("fj:%d ",fj);
    //                    //printf("fa[fi]:%d ",fa[fi]);
    //                    fa[fi]=fj;
    //                    //printf("xiugai fa[fi]:%d\n",fa[fi]);
    //                }
    //            }
            }
        }
        //printf("<<");
    
        // 若所有元素都在一个并查集中，则t满足条件
        int cnt=0;
        for(int i=0;i<n;++i)
        {
            if(fa[i]==i)
            {
                ++cnt;
            }
            if(cnt==2)
            {
                return false;
            }
        }
        return true;
    }
    */
    
    int main()
    {
        
        // 输入
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
        
            scanf("%d %d",&a[i].x,&a[i].y);
        }
        // 初始化距离
        for(int i=1;i<=n;++i)
        {
        
            for(int j=1;j<i;++j)
            {
        
                d[i][j]=d[j][i]=juli(i,j);
            }
        }
        // 二分查找合适的最小时间t
        int l=0,r=999999999,mid,t=0;
        while(l<=r)
        {
        
            //printf(">");
            mid=(r+l)/2;
            //printf("mid:%d",mid);
            if(check(mid)==true)
            {
        
                //printf("true");
                t=mid;
                r=mid-1;
            }
            else
            {
        
                l=mid+1;
            }
            //printf("\n");
        }
        printf("%d",t);
        return 0;
    }