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输入 #12 1 1 6 6输出 #15说明/提示数据范围及约定对于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≤501 ≤ 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 (W1)/2⌈W/2⌉(W1)/2。进一步最小生成树的最大边权等于所有点对之间的“最小瓶颈路径”的最大值。因此可以求出所有点对的最小瓶颈值取其中最大值即为W WW。2. 算法实现Floyd 变体求最小瓶颈路径由于N ≤ 50 N \le 50N≤50数据规模很小可以使用 Floyd 算法的变体求解所有点对之间的最小瓶颈值。初始化距离矩阵dis对于i ≠ j i \ne jijdis[i][j] |x_i - x_j| |y_i - y_j|对角线可设为极大值不影响最终答案因为只统计i j i jij的点对。三重循环松弛dis[i][j] min(dis[i][j], max(dis[i][k], dis[k][j]))该式表示从i ii到j jj的路径以k kk为中转点时路径上的最大边为两段瓶颈值的最大值取所有中转点的最小值即为i ii到j jj的最小瓶颈值。松弛完成后遍历所有i j i jij找出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 jij记录最大瓶颈距离ans。输出输出(ans 1) / 2。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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 i1;in;i)scanf(%lld%lld,a[i].x,a[i].y);for(ll i1;in;i)for(ll j1;jn;j)dis[i][j]1000000000LL;for(ll i1;in-1;i)for(ll ji1;jn;j)dis[i][j]dis[j][i](abs(a[i].x-a[j].x)abs(a[i].y-a[j].y));for(ll k1;kn;k)for(ll i1;in;i)for(ll j1;jn;j)dis[i][j]min(dis[i][j],max(dis[i][k],dis[k][j]));ll ans0;for(ll i1;in-1;i)for(ll ji1;jn;j)if(dis[i][j]ans)ansdis[i][j];printf(%lld\n,(ans1)/2);return0;}