P1661 扩散
网页链接
P1661 扩散
题目描述
一个点每过一个单位时间就会向四个方向扩散一个距离，如图。
两个点a aa、b bb连通，记作e ( a , b ) e(a,b)e(a,b)，当且仅当a , b a,ba,b的扩散区域有公共部分。连通块的定义是块内的任意两个点u , v u,vu,v都必定存在路径e ( u , a 0 ) , e ( a 0 , a 1 ) , ⋯ , e ( a k , v ) e(u,a_0),e(a_0,a_1),\cdots,e(a_k,v)e(u,a0),e(a0,a1),⋯,e(ak,v)。给定平面上的n nn个点，问最早什么时刻它们形成一个连通块。
输入格式
第一行一个正整数N NN，以下N NN行，每行两个以空格分隔的正整数X i , Y i X_i, Y_iXi,Yi，表示平面中一个点的坐标。
输出格式
一个数，表示最早的时刻所有点形成连通块。
输入输出样例 #1
输入 #1
2 1 1 6 6输出 #1
5说明/提示
数据范围及约定
对于20 % 20\%20%的数据，满足1 ≤ N ≤ 5 ; 1 ≤ X i , Y i ≤ 50 1 \le N \le 5;1 \le X_i,Y_i \le 501≤N≤5;1≤Xi,Yi≤50。
对于100 % 100\%100%的数据，满足1 ≤ N ≤ 50 1 \le N \le 501≤N≤50，1 ≤ X i , Y i ≤ 10 9 1 \le X_i,Y_i \le 10^91≤Xi,Yi≤109。
解题思路
本题是最小瓶颈生成树 + 扩散时间的经典问题。给定平面上N NN个点，每个单位时间点会向上下左右扩散一个单位，求所有点形成连通块的最早时刻。两个点连通当且仅当它们的扩散区域有公共部分，这等价于它们之间的曼哈顿距离不超过两倍时间。
1. 问题等价转化
- 设点i ii与点j jj的曼哈顿距离为D i j = ∣ x i − x j ∣ + ∣ y i − y j ∣ D_{ij} = |x_i-x_j| + |y_i-y_j|Dij=∣xi−xj∣+∣yi−yj∣。
从时刻0 00开始，两个点的扩散区域会在时间t tt发生重叠，当且仅当2 t ≥ D i j 2t \ge D_{ij}2t≥Dij，即t ≥ ⌈ D i j / 2 ⌉ t \ge \lceil D_{ij}/2 \rceilt≥⌈Dij/2⌉。 - 因此，若将每个点视为图中的一个节点，任意两点间边的权值设为它们的曼哈顿距离D i j D_{ij}Dij，则原问题转化为：求一个最小的时刻T TT，使得在时间T TT时所有点通过扩散互相连通。
这等价于在完全图中求最小生成树，树的最大边权W WW决定了最后连通的时间，答案为⌈ W / 2 ⌉ = ( W + 1 ) / 2 \lceil W/2 \rceil = (W+1)/2⌈W/2⌉=(W+1)/2。 - 进一步，最小生成树的最大边权等于所有点对之间的“最小瓶颈路径”的最大值。因此，可以求出所有点对的最小瓶颈值，取其中最大值即为W WW。
2. 算法实现：Floyd 变体求最小瓶颈路径
由于N ≤ 50 N \le 50N≤50，数据规模很小，可以使用 Floyd 算法的变体求解所有点对之间的最小瓶颈值。
- 初始化距离矩阵
dis：- 对于i ≠ j i \ne ji=j，
dis[i][j] = |x_i - x_j| + |y_i - y_j|； - 对角线可设为极大值，不影响最终答案（因为只统计i < j i < ji<j的点对）。
- 对于i ≠ j i \ne ji=j，
- 三重循环松弛：
该式表示从i ii到j jj的路径，以k kk为中转点时，路径上的最大边为两段瓶颈值的最大值；取所有中转点的最小值即为i ii到j jj的最小瓶颈值。dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j])) - 松弛完成后，遍历所有i < j i < ji<j，找出
dis[i][j]的最大值，记为ans。 - 最终答案
(ans + 1) / 2，即曼哈顿距离的一半向上取整。
3. 复杂度分析
- 时间复杂度：Floyd 三重循环O ( N 3 ) O(N^3)O(N3)，N ≤ 50 N \le 50N≤50，计算量极小。
- 空间复杂度：O ( N 2 ) O(N^2)O(N2)存储距离矩阵，完全可行。
总结
通过 Floyd 变体求出所有点对之间的最小瓶颈路径，取其中的最大值即为最小生成树的最大边权。由于扩散问题中两个点实际连通时间为曼哈顿距离的一半（上取整），最终输出(ans + 1) / 2。该方法简洁高效，适合小规模数据。
代码简要说明
- 结构体
node：存储点的坐标x和y。 - 初始化：读入N NN和所有点坐标，将
dis[i][j]设为两点间曼哈顿距离（i ≠ j i \ne ji=j），对角线置为大数。 - Floyd 变体：三重循环用
max和min更新瓶颈值。 - 找最大值：遍历所有i < j i < ji<j，记录最大瓶颈距离
ans。 - 输出：输出
(ans + 1) / 2。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structnode{ll x,y;}a[105];ll dis[105][105];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)dis[i][j]=1000000000LL;for(ll i=1;i<=n-1;i++)for(ll j=i+1;j<=n;j++)dis[i][j]=dis[j][i]=(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y));for(ll k=1;k<=n;k++)for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));ll ans=0;for(ll i=1;i<=n-1;i++)for(ll j=i+1;j<=n;j++)if(dis[i][j]>ans)ans=dis[i][j];printf("%lld\n",(ans+1)/2);return0;}
