90 求调

#include<bits/stdc++.h>
using namespace std;

/*
	1.牧区：点
	2.牧场：连通块
	3.至少有两个牧区通过任何路径都不连通：意味着给定的图至少有两个连通块
	4.对称邻接矩阵：表明给定图是无向图或双向图
		注意：矩阵的对称轴是该矩阵的左上角到右下角的这条线
	5.n<=150：说明本题要使用floyd算法求最短路
	
	本题做题时可能会存在的如下困难点
	1.如何加边？邻接矩阵可以较为方便的加边和删边
		但是邻接表只能加边不能删边
		而绝大多数题目要求加完边以后还要删掉。且绝大多数题目的n比较大，不能用邻接矩阵存
		意味着我们就必须考虑【能完成加边效果的假加边操作】
	2.什么样的两个点才能加边？
		两个不在一个连通块的点可以加边
	3.如果确定两个点不在一个连通块？
		可以使用求完最短路以后的g[][]是否==0x3f3f3f3f进行判断
			（由于本题的边长都非负）
		而不可以使用最开始还没进行floyd求最短路之前的原始邻接矩阵
			因为原始的邻接矩阵g[i][j]仅表示i是否可以直达j
	4.根据第三点：我们要扫描整个求完floyd之后的g[][]来确定当前的i,j之间是否连通
		如果不联通，就意味着该两点属于不同的连通块
	5.floyd的作用是可以求出任意两点之间的最短路。
		说明，即便该图中存在多个互不相连的连通块
		floyd仍然可以求出每个连通块内部的任意两点之间的最短路
	6.一次尝试枚举所有的不在同一个连通块的两个节点
		由于本题是双向图，因此枚举的范围分别是i:1~n, j: i+1~n
	7.对于某一次的加边操作：
		连通该两点i,j以后，就形成了一个新的大连通块，则该大联通块就有自己的新直径
		--当然，新直径并不一定更大。
		假设i所在连通块为A，j所在的联通块为B，则 
		(1)新直径仍然在原来的某一个连通块中取到，也有可能存在多个直径
		(2)可能变得更大：如果变得更大的话，则意味着此时的新的更大的直径，
			其对应的最短路径的两个端点之间的最短路的路径，一定途经加边的两点i,j 
			且这个新直径的值计算方式如下：x+y+w
			其中：
			x为在A中以i为起点到达A中其他节点的最短路的最大值
			y为在B中以j为起点到达B中其他节点的最短路的最大值
			w为新添加的边i-j之间的直达距离
		(3)由于最大值可能是(1)，也可能是(2)
			因此对于每添加的一条边，都进行取二者的最大值
		(4)最终题目要求的答案就是全局的最大值中的最小值
	8.如何计算x,y？x和y的求法一样。故以求解x为例
		在求完floyd以后，在g[][]的第i行，比较得出所有的不为∞的值的最大值就是x
	9.旧直径怎么求？
		如果是研究求完floyd以后的g[][]中i所在的行有哪些列的值不为∞，
		然后再依次枚举出全部的这些两个节点对，则最差情况下还需要n*n次
		再加上我们在外面枚举i,j的双层循环，复杂度为n*n*n*n,会超时
		所以效率更高的做法为：
		对于每一个连通块，维护一个并查集，并查集的根节点记录该连通块的直径即可
	10.如何维护这个并查集。【每一个并查集完全对应一个连通块】 
		分析发现，在维护并查集时，对于每一个联通内的i,j最短路取最大值维护即可 
	11.小优化：可以事先预计算出每一个i对应x
*/ 

int n;

double g[160][160]; // 必须为double类型

typedef pair<int,int> PII;

PII pt[160];

double mx[160]; // 必须为double类型

double getdist(PII a, PII b){
	return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(g[i][k]+g[k][j]<g[i][j]) g[i][j]=g[i][k]+g[k][j];
			}
		}
	}
}

int p[160];
double dm[160]; // dm[]数组具备懒惰性，当且仅当p[i]==i时，dm[i]才表示i所在连通块的直径 
	// 注意开成double类型

int find(int x){
	if(x!=p[x]){
		int zu=find(p[x]);
		p[x]=zu;
	}
	return p[x];
}

int main(){

	cin>>n;
	for(int i=1;i<=n;i++) p[i]=i; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j) g[i][j]=0x3f3f3f3f;
		}
	}
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		pt[i]=(PII){x,y};
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char ch;
			cin>>ch;
			if(ch=='1') g[i][j]=min(g[i][j],getdist(pt[i],pt[j]));

		}

	}
	floyd();
	
	// 预计算每一个点对应的mx[i],顺便可以把并查集给维护出来
	// ===此操作不涉及到加边 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(fabs(g[i][j]-0x3f3f3f3f)>1e-1){ // 此时i和j在一个连通块中
				mx[i]=max(mx[i],g[i][j]);
					// 寻找i所长在的连通块中，从i出发能到达的其余各点的最短路的最大值
				int gi=find(i);
				int gj=find(j);
				if(gi!=gj){
					// 更新合并之后的并查集对应的新连通块的直径
					p[gi]=gj;
					dm[gj]=max(dm[gi],dm[gj]);
					dm[gj]=max(dm[gj],g[i][j]);
						// 在同一个连通块中每一个点对的最短距离都会被比较取最大值
						// 因此就能得到该连通块的最大直径了 
				}
			}
		}
	}
	
//	for(int i=1;i<=n;i++) cout<<mx[i]<<' ';
//	cout<<"====="<<endl;
	
	double mi=0x3f3f3f3f;
	
	// 枚举所有可以加的边
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			// 尝试在第i个点和第j个点之间连边
			// 能力岸边的前提是不在一个连通块中
			if(fabs(g[i][j]-0x3f3f3f3f)<1e-6){ // 不在一个连通块时才可以加边 
				
				int gi=find(i);
				int gj=find(j);
				
				double ma=max(dm[gi],dm[gj]); 
				double newlen=mx[i]+mx[j]+getdist(pt[i],pt[j]); // x+y+w;
				ma=max(ma,newlen);
				mi=min(mi,ma);
			} 
		}
	} 
	
	printf("%.6f\n",mi);
	
	return 0; 
}