先用floyd 求两点之间的最短距离map[i][j] ，再求各点与牧区内其他结点距离的最大值d[i]。
枚举分别在两个牧区的两个点i,j，
tmp = d[i] + d[j] + ( i, j 之前的距离）
/**//*
ID: lorelei
TASK: cowtour
LANG: C++
*/
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <memory.h>
using namespace std;
const double INF = 999999.0;
typedef pair<int, int> PAIR;
PAIR loc[200];
double map[200][200];
double d[200];
int N;
inline double dist(int x1, int y1, int x2, int y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
int main(){
int i,j,k;
double ans= INF;
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
fin>>N;
for(i=0; i<N; ++i)
fin>>loc[i].first>>loc[i].second;
char ch;
for(i=0; i<N; ++i)
for(j=0; j<N; ++j){
fin>>ch;
if(ch=='1')
map[i][j] = map[j][i] = dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
else if(ch=='0')
map[i][j] = map[i][j] = INF;
if(i==j)
map[i][j] = 0;
}
for(k=0; k<N; ++k)
for(i=0; i<N; ++i)
for(j=0; j<N; ++j)
if(map[i][j] > map[i][k]+map[k][j])
map[i][j] = map[i][k]+map[k][j];
memset(d, 0, sizeof(d));
for(i=0; i<N; ++i)
for(j=0; j<N; j++)
if(map[i][j]>d[i] && map[i][j]!=INF)
d[i] = map[i][j];
for(i=0; i<N; ++i)
for(j=0; j<N; ++j)
if(map[i][j]==INF){
double tmp = d[i]+d[j]+dist(loc[i].first, loc[i].second, loc[j].first, loc[j].second);
if(tmp<ans)
ans = tmp;
}
for(i=0; i<N; ++i)
if(d[i]>ans)
ans = d[i];
fout<<setprecision(6)<<setiosflags(ios::fixed | ios::showpoint)<<ans<<endl;
return 0;
}posted on 2010-12-10 19:49
小阮 阅读(187)
评论(0) 编辑 收藏 引用 所属分类:
USACO