1437：扩散

1437：扩散(一本通网站原题链接)

【分析】

　　本题初看很是高兴，虽然数值较大，但数据量很小，随便折腾都不会超时。再看本题所需解决的问题，1：如何确定点的连通。这个问题很熟悉，之前高中数学中有一个题目：在画有方格的纸上有两个格点A、B，一只蚂蚁从A沿网格线爬到B的最短路径有多少条。其实就是横格与竖格的排列。这个就更简单了，数横格与竖格的和作为两点的距离。两个点都在扩散，相当于速度为2，经过多少时间可以连通就可以计算了。2：图的连通性。这个有模式了，可以用集合的方法。我用的集合合并的方法，全图连通了，每个点的祖先都一样，每个点的祖先的成员个数就是n。3：最少时间的计算。这个几乎是个倒序了。其实我们应该是知道时间才知道点的连通性，也才知道图的连通性，所以，我们可以用二分法试确定。

　　整体来看，这个题目还是不错的，虽然没有超时的危险，但对基础方法算是个复习。

【AC代码】

//1437：扩散
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int const N=101,inf=0x7fffffff;
ll x[N],y[N],d[N][N],fa[N],num[N],n,l=inf,r,ti,tj,mid;
int pa(int tx)
{
    if(fa[tx]!=tx)fa[tx]=pa(fa[tx]);
    return fa[tx];
}
bool ts(int t)
{
    for(int i=1;i<=n;i++)fa[i]=i,num[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(d[i][j]<=t*2)
            {
                ti=pa(i);
                tj=pa(j);
                if(ti!=tj)
                fa[tj]=ti,num[ti]+=num[tj];
            }
    return num[pa(1)]==n;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            d[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j]);
            if(l>d[i][j])l=d[i][j];
            if(r<d[i][j])r=d[i][j];
        }
    l/=2,r=(r+1)/2;
    while(l+1<r)
    {
        mid=(l+r)/2;
        if(ts(mid))r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}

1437：扩散

1437：扩散(一本通网站原题链接)

推荐阅读