最小生成树+思维 扩散（洛谷 P1661）

扩散

题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

图略

两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。

输入格式

第一行一个数n，以下n行，每行一个点坐标。

输出格式

一个数，表示最早的时刻所有点形成连通块。

输入输出样例平面上的n给点，问最早什么时刻它们形成一个连通块。

首先要知道两点的最短时间成连通块就是两点的哈曼顿距离，这是最关键的；
然后就是求这n个点的最小生成树的最长边；

代码：

#include<bits/stdc++.h>
#define LL long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=100100;
const int M=2000100;
const int mod=1e9;
int head[N],cnt,n,x[100],y[100],fa[100];
struct Node{
	int fa,sn,w;
}edge[N*2];
void add(int p,int q,int w){
	edge[cnt].fa=p;
	edge[cnt].sn=q;
	edge[cnt].w=w;
	cnt++;
}
bool cmp(Node p,Node q){return p.w<q.w;}
int find(int p){
	if(p==fa[p]) return p;
	return fa[p]=find(fa[p]);
}
int krus(){
	sort(edge,edge+cnt,cmp);
	int tot=0,ans=0;
	for(int i=0;i<cnt;i++){
		if(find(edge[i].fa)!=find(edge[i].sn)){
			tot++;
			fa[find(edge[i].sn)]=find(edge[i].fa);
			ans=max(edge[i].w,ans);
		}		
		if(tot==n-1) break;
	}
	return ans;
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n;
	for(int i=1;i<=n;i++) fa[i]=i;
	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++){
			int d=abs(x[j]-x[i])+abs(y[j]-y[i]);
			d=(d+1)/2;
			add(i,j,d),add(j,i,d);
		}
	}
	cout<<krus()<<endl;
	return 0;
}