题解 P1522 【牛的旅行 Cow Tours】

· · 题解

题面分析

牧区就是一个点，牧场是多个（或一个）点构成的联通块，每个牧区的坐标将以(x,y)坐标的方式给出，两点之间的连通性将以对称的01矩阵给出，所以可以理解为无向边。

现在请将两个不连通的牧区相连，形成一个大牧场，使得这个大牧场的直径最小，一个牧场的直径就是牧场中最远的两个牧区的距离

算法分析

最短路好题，细节挺多的，因为N\leq 150很小，所以说各位都能想到要跑Floyd

跑完Floyd之后我们怎么做呢

我们容易想到枚举出每一个点能到的最远的点的距离，存到Far[i]里

然后暴力枚举不联通的两点i,j，求出答案Far[i]+Far[j]+Distance(i,j)

然而这是错的，可以被下面这个卡掉

    @@@
    @1@
    @@@
     |   @@@
     |   @4@
 100 |   @@@
     |  
     |  
    @@@          @@@
    @2@----------@3@
    @@@   100    @@@

已知4到2距离w显然小于100

如果我们这个时候连2,4这样按照公式我们会得到错误答案

Far[i]+Far[j]+Distance(i,j)=100+0+w<200

显然连2,4的直径应该是1->2->3=200

我们少考虑了一点：新的大牧场的直径不一定比原来的两个牧场大

所以我们首先统计每个连通块的直径Blockd[i]，对于寻找连通块，直接dfs就行了

所以对于真正的答案应该是max\{Far[i]+Far[j]+Distance(i,j) ,Blockd[i],Blockd[j]\}，其中i,j不在同一连通块

善意的提醒

代码

#include<cstdio>
#include<cstdlib>
#include<cstdarg>
#include<iostream>
#include<cmath>

#define rg register
#define il inline
#define MX (150 + 5)
#define INF (123456789)

double min(double x ,double y){return x < y ? x : y;}
double max(double x ,double y){return x > y ? x : y;}
//记得double

int n;

struct farm{
    int x ,y;
    double distance(const farm &b){
        return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y));
    }
}p[MX];

double dis[MX][MX] ,farthest[MX];
//dis是最短路
//farthest是上文的far，即每一个点能到的最远的点的距离
void Floyd(){
    for(rg int k = 1 ; k <= n ; ++k){
        for(rg int i = 1 ; i <= n ; ++i){
            for(rg int j = 1 ; j <= n ; ++j){
                dis[i][j] = min(dis[i][j] ,dis[i][k] + dis[k][j]);
            }
        }
    }
}

int linkcnt;    //连通块的个数
double Blockmax[MX];    //某个连通块中的farthest最大值
int refer[MX];  //表示某个点所在的连通块编号
void dfs(int x){
    if(refer[x])    return;
    refer[x] = linkcnt;
    for(rg int i = 1 ; i <= n ; ++i)
        if(dis[x][i] < INF) dfs(i);
        //dis < INF即代表有边
}
int main(){
    scanf("%d" ,&n);
    for(rg int i = 1 ; i <= n ; ++i){
        scanf("%d%d" ,&p[i].x ,&p[i].y);
    }
    for(rg int i = 1 ,op ; i <= n ; ++i){
        for(rg int j = 1 ; j <= n ; ++j){
            dis[i][j] = INF;    //记得设初始值INF
            scanf("%1d" ,&op);
            if(op){
                dis[i][j] = p[i].distance(p[j]);
            }
            if(i == j)  dis[i][j] = 0;//自己到自己dis是0
        }
    }
    Floyd();
    for(rg int i = 1 ; i <= n ; ++i)    //寻找连通块
        if(!refer[i]){++linkcnt;dfs(i);}
    for(rg int i = 1 ; i <= n ; ++i){   //求出farthest
        for(rg int j = 1 ; j <= n ; ++j){
            if(dis[i][j] < INF){    //dis < INF即代表有边
                farthest[i] = max(farthest[i] ,dis[i][j]);
            }
        }
    }
    for(rg int i = 1; i <= linkcnt ; ++i){  //对于每一个连通块求出直径
        double kuaimax = -INF;  //记得设置-INF
        for(rg int j = 1 ; j <= n ; ++j){
            if(refer[j] == i)   kuaimax = max(kuaimax ,farthest[j]);
        }
        Blockmax[i] = kuaimax;
    }
    double ans = INF;   //记得设置INF
    for(rg int i = 1 ; i <= n ; ++i){
        for(rg int j = 1 ; j <= n ; ++j){
            if(refer[i] != refer[j]){   //两者不能在同一连通块
                ans = min(ans ,max(p[i].distance(p[j]) + farthest[i] + farthest[j] ,max(Blockmax[refer[i]] ,Blockmax[refer[j]])));
            }
        }
    }
    printf("%.6lf \n" ,ans);
    return 0;
}