这题综合了dfs,floyd算法。
首先用 floyd计算出两两之间的最短路径。然后用dfs将图着色。对每两两不同颜色的结点，我们把它们相连，然后看产生的图的直径的大小。
直径的大小只可能仍为原两连通图直径之一，或者是包括新添加的路径所产生的最长路径，取这三者中的最大值。新路径产生的最长路径只可能是两点的距离加上两点到其他点的最长距离。最开始的时候只考虑了新添加的路径，没考虑原直径会比新路径大的情况，wa了n次。。
#include <iostream>
#include <fstream>
#include <cfloat>
#include <cmath>
using namespace std;
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
double path[150][150];
char graph[150][150];
int x[150];
int y[150];
int n;
int color[150];
double diameter[150];
double maxPath[150];
void floyd()
{
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
if(i!=j){
path[i][j]=min(path[i][j],path[i][k]+path[k][j]);
}
}
}
void make_color(int i,int c)
{
if( color[i]!=0 )
return;
color[i] = c;
for(int j=0;j<n;++j){
if(color[j]==0&&graph[i][j])
make_color(j,c);
}
}
void solve()
{
in>>n;
for(int i=0;i<n;++i){
in>>x[i]>>y[i];
}
for(int i=0;i<n;++i){
string s;
in>>s;
for(int j=0;j<n;++j){
graph[i][j]=s[j]-'0';
if(graph[i][j]){
path[i][j] = sqrt( (x[i]-x[j])*(x[i]-x[j])
+(y[i]-y[j])*(y[i]-y[j]) );
}else{
path[i][j] = DBL_MAX/4;
}
}
}
floyd();
int c = 0;
for(int i=0;i<n;++i)
if(color[i]==0)
make_color(i,++c);
for(int i=0;i<n;++i){
maxPath[i] = 0;
for(int j=0;j<n;++j){
if(i!=j&&color[i]==color[j]){
maxPath[i] = max(maxPath[i],path[i][j]);
}
}
diameter[color[i]] = max(diameter[color[i]],maxPath[i]);
}
double dia = DBL_MAX;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j){
if(color[i]==color[j]) continue;
double d1 = 0;
for(int p=0;p<n;++p){
if(i!=p&&color[i]==color[p])
d1 = max(d1,path[i][p]);
}
double d2 = 0;
for(int p=0;p<n;++p){
if(j!=p&&color[j]==color[p])
d2 = max(d2,path[j][p]);
}
double dist = sqrt( (x[i]-x[j])*(x[i]-x[j])+
(y[i]-y[j])*(y[i]-y[j]) );
dia = min(dia,max(d1+d2+dist,max(diameter[color[i]],diameter[color[j]])) );
}
out.setf(ios::fixed,ios::floatfield);
out.precision(6);
out<<dia<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}