這題綜合了dfs,floyd算法。
首先用 floyd計(jì)算出兩兩之間的最短路徑。然后用dfs將圖著色。對(duì)每?jī)蓛刹煌伾慕Y(jié)點(diǎn)，我們把它們相連，然后看產(chǎn)生的圖的直徑的大小。
直徑的大小只可能仍為原兩連通圖直徑之一，或者是包括新添加的路徑所產(chǎn)生的最長(zhǎng)路徑，取這三者中的最大值。新路徑產(chǎn)生的最長(zhǎng)路徑只可能是兩點(diǎn)的距離加上兩點(diǎn)到其他點(diǎn)的最長(zhǎng)距離。最開(kāi)始的時(shí)候只考慮了新添加的路徑，沒(méi)考慮原直徑會(huì)比新路徑大的情況，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;
}