二分+最小生成树（kruskal使用并查集）
不清楚的题意导致我被坑了qwq，其实间接联通也是允许的。所以可以使用并查集+最小生成树维护
每次二分答案，然后跑一遍最小生成树判断是否联通。
end.
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; struct edge{ int from,to,dis; }a[2502]; int n,cnt,x[52],y[52],fa[52]; inline int find(int x) {return fa[x]==x ? fa[x]:fa[x]=find(fa[x]);} //路径压缩 inline void uni(int x,int y){ int r1=find(fa[x]),r2=find(fa[y]); if(r1!=r2) fa[r1]=r2; }//并查集基本操作：find，uni。一个找父亲，一个连父亲 inline bool cmp(const edge &A,const edge &B) {return A.dis<B.dis;} int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]); for(int i=1;i<n;++i) for(int j=i+1;j<=n;++j) a[++cnt]=(edge){i,j,abs(x[i]-x[j])+abs(y[i]-y[j])};//曼哈顿距离计算 sort(a+1,a+cnt+1,cmp); //按权值升序排 int l=0,r=1e9,mid,k; while(l<r){ mid=l+((r-l)>>1); k=0; for(int i=1;i<=n;++i) fa[i]=i; //重置父亲 for(int i=1;i<=cnt;++i){ if(a[i].dis>(mid<<1)) break; //注意两个点都在扩展，所以要*2 if(find(a[i].from)!=find(a[i].to)) uni(a[i].from,a[i].to),++k; if(k==n-1) break; //剪枝 }//kruskal最小生成树 if(k!=n-1) l=mid+1; //不符合条件 else r=mid; } printf("%d",l); return 0; }