扩散（信息学奥赛一本通 1437）（洛谷 1661）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+5;
 4 int x[N],y[N],fa[N],d[100][100];
 5 int n;
 6 int m,q,ans,p,tot;
 7 int read()
 8 {
 9     int f=1;char ch;
10     while((ch=getchar())<‘0‘||ch>‘9‘)
11         if(ch==‘-‘)f=-1;
12     int res=ch-‘0‘;
13     while((ch=getchar())>=‘0‘&&ch<=‘9‘)
14         res=res*10+ch-‘0‘;
15     return res*f;
16 }
17 void write(int x)
18 {
19     if(x<0)
20     {
21         putchar(‘-‘);
22         x=-x;
23     }
24     if(x>9)write(x/10);
25     putchar(x%10+‘0‘);
26 }
27 
28 
29 int main()
30 {
31     n=read();
32     for(int i=1;i<=n;i++)
33         x[i]=read(),y[i]=read();
34     for(int i=1;i<n;i++)
35         for(int j=i+1;j<=n;j++)
36             d[i][j]=d[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
37     for(int k=1;k<=n;k++)
38         for(int i=1;i<=n;i++)
39             if(k!=i)
40                 for(int j=1;j<=n;j++)
41                     if(j!=k&&j!=i)
42                         d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
43     for(int i=1;i<n;i++)
44         for(int j=i+1;j<=n;j++)
45             ans=max(ans,d[i][j]);
46     write((ans+1)/2);
47     return 0;
48 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+5;
 4 int x[N],y[N],fa[N],d[100][100];
 5 int n;
 6 int m,q,w,ans,p,tot;
 7 int read()
 8 {
 9     int f=1;char ch;
10     while((ch=getchar())<‘0‘||ch>‘9‘)
11         if(ch==‘-‘)f=-1;
12     int res=ch-‘0‘;
13     while((ch=getchar())>=‘0‘&&ch<=‘9‘)
14         res=res*10+ch-‘0‘;
15     return res*f;
16 }
17 void write(int x)
18 {
19     if(x<0)
20     {
21         putchar(‘-‘);
22         x=-x;
23     }
24     if(x>9)write(x/10);
25     putchar(x%10+‘0‘);
26 }
27 int find(int x)
28 {
29     if(fa[x]!=x)fa[x]=find(fa[x]);
30     return fa[x];
31 }
32 bool check(int t)
33 {
34     for(int i=1;i<=n;i++)fa[i]=i;
35     for(int i=1;i<n;i++)
36         for(int j=i+1;j<=n;j++)
37             if(d[i][j]<=t*2)
38             {
39                 int fx=find(i),fy=find(j);
40                 if(fx!=fy)fa[fy]=fx;
41             }
42     int sum=0;
43     for(int i=1;i<=n;i++)
44     {
45         if(fa[i]==i)sum++;
46         if(sum==2)return false;
47     }
48     return true;
49 }
50 int main()
51 {
52     n=read();
53     for(int i=1;i<=n;i++)
54         x[i]=read(),y[i]=read();
55     for(int i=1;i<n;i++)
56         for(int j=i+1;j<=n;j++)
57             d[i][j]=d[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
58     int l=0,r=999999999;
59     while(l<=r)
60     {
61         int mid=l+r>>1;
62         if(check(mid))r=mid-1,ans=mid;
63         else l=mid+1;
64     }
65     write(ans);
66     return 0;
67 }