首页 > 其他 > 详细

USACO Cow Tours

时间:2015-12-27 12:13:15      阅读:281      评论:0      收藏:0      [点我收藏+]

  大体的意思就是给你至少两个连通块, 你可以在两个不同的连通块之间连一条边, 找出连了一条边以后连通块的最短直径(连通块中相距最远的两点), 有一点比较坑, 看代码:

/*
    ID: m1500293
    LANG: C++
    PROG: cowtour
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const double inf = 1e20;
int N;
int x[155], y[155];
double dist[155][155];

double getdist(int i, int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void floyd()
{
    for(int k=1; k<=N; k++)
    for(int i=1; i<=N; i++)
    for(int j=1; j<=N; j++)
    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
}

double farest[155];

int main()
{
    freopen("cowtour.in", "r", stdin);
    freopen("cowtour.out", "w", stdout);
    scanf("%d", &N);
    for(int i=1; i<=N; i++)
        scanf("%d%d", &x[i], &y[i]);
    for(int i=1; i<=N; i++)
    for(int j=1; j<=N; j++)
    {
        if(i==j) dist[i][j] = 0;
        else dist[i][j] = inf;
        int t;
        scanf("%1d", &t);
        if(t)
        {
            dist[i][j] = getdist(i, j);
        }
    }
    floyd();
    for(int i=1; i<=N; i++)
    {
        farest[i] = 0;
        for(int j=1; j<=N; j++) if(dist[i][j]!=inf)
            farest[i] = max(farest[i], dist[i][j]);
    }
    double res = inf;
    for(int i=1; i<=N; i++)
    {
        for(int j=i+1; j<=N; j++)
            if(dist[i][j]==inf)
                res = min(res, getdist(i, j)+farest[i]+farest[j]);
    }
    for(int i=1; i<=N; i++)     //注意这里, 有坑,可能出现一个块中只有一个点的情况
    if(farest[i] > res) res = farest[i];
    printf("%.6f\n", res);
    return 0;
}

 

USACO Cow Tours

原文:http://www.cnblogs.com/xingxing1024/p/5079720.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!