1437 扩散题目大意给定平面上的 $n$ 个点每过一个单位时间每个点都会向四个方向扩散一个距离求它们形成连通块的最短时间。知识要点二分、并查集、生成树解题思路 1两个点之间直接连通的时间就是它们曼哈顿距离的一半可以二分枚举时间利用并查集检查是否所有节点均连通。参考代码 1#includebits/stdc.husingnamespacestd;constintN55;intn,x[N],y[N],fa[N];intfind(intx){if(fa[x]x)returnx;returnfa[x]find(fa[x]);}boolcheck(intt){for(inti1;in;i)fa[i]i;for(inti1;in;i)for(intji1;jn;j){if(abs(x[i]-x[j])abs(y[i]-y[j])2*t)fa[find(i)]find(j);}intcnt0;for(inti1;in;i)if(fa[i]i)cnt;returncnt1;}intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d%d,x[i],y[i]);intl0,r1e9,t;while(lr){t(lr)/2;if(check(t))rt;elselt1;}printf(%d\n,l);return0;}解题思路 2所有的点都连通意味着至少形成了一棵生成树需要的时间就是最长的那条边相当于求完全图的一个最小瓶颈树使用 Prim 算法的时间复杂度为 $O(n^2)$。参考代码 2#includebits/stdc.husingnamespacestd;constintN55;intn,x[N],y[N],v[N],dis[N];intPrim(){intans0;memset(dis,0x3f,sizeof(dis));dis[1]0;for(intk1;kn;k){inti0,j;for(j1;jn;j)if(!v[j]dis[i]dis[j])ij;v[i]1,ansmax(ans,dis[i]);for(j1;jn;j)if(!v[j])dis[j]min(dis[j],abs(x[i]-x[j])abs(y[i]-y[j]));}returnans;}intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d%d,x[i],y[i]);printf(%d\n,(Prim()1)/2);return0;}