记录编号	51626	评测结果	AAAAAAAAA
题目名称	[USACO 2.4.3]牛的旅行	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2012-12-27 20:29:30	内存使用	0.52 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<iomanip>
using namespace std;
const int SIZE=151;
const double INF=0xffffff;
class point{
	public:
	double x;
	double y;
}ran[SIZE];//每点坐标
int n,sum;
int area[SIZE]={0};//每点所属牧场
double leng[SIZE][SIZE]={0},longest[SIZE]={0},dia[SIZE]={0};//两点距离,每点到所属牧场中最远点的距离,牧场直径
//需先在leng中存入邻接矩阵，其余填充为INF,顶点下标为0~n-1
bool con[SIZE][SIZE]={0};//两点是否相邻
double ans=INF;
double ldis(int a,int b){//两点间直线距离
	double xd=ran[a].x-ran[b].x,yd=ran[a].y-ran[b].y;
	return sqrt(xd*xd+yd*yd);
}
void floyd(void){//都懂吧
	int i,j,k;
	for(k=0;k<n;k++){
		for(i=0;i<n;i++){
			if(area[i]!=area[k]||leng[i][k]==INF) continue;
			for(j=0;j<n;j++){
				if(area[k]!=area[j]||leng[k][j]==INF) continue;
				if(leng[i][k]+leng[k][j]<leng[i][j]) leng[i][j]=leng[i][k]+leng[k][j];
			}
		}
	}
}
void BFS_point(int x,int p){//搜x所在联通块,牧场号为p
	queue<int> s;
	s.push(x),area[x]=p;
	int i,temp;
	while(!s.empty()){
		temp=s.front(),s.pop();
		for(i=0;i<n;i++){
			if(i!=temp&&con[temp][i]&&area[i]==0) s.push(i),area[i]=p;
		}
	}
}
void BFS(void){//搜连通性
	int i,p=1;
	for(i=0;i<n;i++){
		if(area[i]==0) BFS_point(i,p++);
	}
	sum=p-1;
}
void diameter(void){//求每个牧场的直径
	int i,j,k;
	double amax,pmax;//牧场/当前点的最远距离
	for(i=1;i<=sum;i++){
		amax=0;
		for(j=0;j<n;j++){
			pmax=0;
			if(area[j]!=i) continue;
			for(k=0;k<n;k++){
				if(j==k||area[k]!=i) continue;
				if(leng[j][k]!=INF&&leng[j][k]>pmax) pmax=leng[j][k];
			}
			if(pmax>amax) amax=pmax;
			longest[j]=pmax;
		}
		dia[i]=amax;
	}
}
void add(void){//枚举添加道路后的情况
	int i,j;
	double nowdis,max;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(area[i]==area[j]) continue;
			nowdis=ldis(i,j);
			max=nowdis+longest[i]+longest[j];
			if(dia[area[i]]>max) max=dia[area[i]];
			if(dia[area[j]]>max) max=dia[area[j]];
			if(max<ans) ans=max;
		}
	}
}
void input(void){
	int i,j,x,y;
	char s[200]={0};
	/*就尼玛为了个\n啊!!!!!尼玛getchar怒跪啊!!!!尼玛提了26遍才幡然悔悟用数组啊!!!!!!!!
	尼玛linux的行输入得有多坑爹啊!!!!!!!!!!!!!!!!!!!!!*/
	//那啥,数组就数组吧......我是在没劲改成string了......
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d%d",&x,&y),ran[i].x=(double)x,ran[i].y=(double)y;
	for(i=0;i<n;i++){
		cin>>s;
		for(j=0;j<n;j++){
			con[i][j]=(s[j]=='1')?1:0;
			if(i==j){
				con[i][j]=1,leng[i][j]=0;
			}
			else{
				if(!con[i][j]) leng[i][j]=INF;
				else leng[i][j]=ldis(i,j);
			}
		}
	}
}
int main(){
	freopen("cowtour.in","r",stdin);
	freopen("cowtour.out","w",stdout);
	input();
	BFS();
	floyd();
	diameter();
	add();
	cout<<setiosflags(ios::fixed)<<setprecision(6)<<ans<<endl;
	return 0;
}