USACO 2.4.3 Cow Tours 牛的旅行

这道题给的数据，直接就是一个邻接矩阵。先求最短路，用Floyd就可以了。

算出所有牧场的直径，记其中最大值为pmax

每个牧区就是一个连通分支，枚举每个点对(a,b)

枚举(a,b)分为位于不同的连通分支，计算连接上以后的形成的新的连通分支的直径，就是a,b距离再加上a,b分别位于的分支的直径。然后从所有的点对中找到连接以后形成最小直径的牧区记为pmin。

如果 pmin>pmax那么就要输出pmin，这种情况表示新形成的牧区比原来的所有牧区都大否则输出pmax

/*
ID: cmykrgb1
PROG: cowtour
LANG: C++
*/
#include <stdio.h>
#include <math.h>
#define ITF (1e40)

FILE *fi,*fo;
long n;
double dis[200][200],dt[200];
long px[200],py[200];

double dist(long& x1,long& y1,long& x2,long& y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}

void floyed()
{
    long i,j,k;
    for (k=1;k<=n;k++)
    {
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            {
                if (dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    for (i=1;i<=n;i++)
        dis[i][i]=ITF;
}

int main(void)
{
    long i,j,a;
    double pmax,pmin,tmp,max=0;
    fi=fopen("cowtour.in","r");
    fo=fopen("cowtour.out","w");
    fscanf(fi,"%ld",&n);
    for (i=1;i<=n;i++)
    {
        fscanf(fi,"%ld%ld",&px[i],&py[i]);
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            a=10;
            while (a==10 || a==13)
                a=getc(fi);
            a-=48;
            if (a)
            {
                dis[i][j]=dist(px[i],py[i],px[j],py[j]);
            }
            else
            {
                dis[i][j]=ITF;
            }
        }
    }
    floyed();

    for (i=1;i<=n;i++)
    {
        pmax=0;
        for (j=1;j<=n;j++)
        {
            if (dis[i][j]>pmax && dis[i][j]!=ITF)
                pmax=dis[i][j];
        }
        dt[i]=pmax;
        if (pmax>max) max=pmax;
    }
    pmin=ITF;
    for (i=1;i<=n-1;i++)
    {
        for (j=i+1;j<=n;j++)
        {
            if (dis[i][j]==ITF && i!=j)
            {
                tmp=dist(px[i],py[i],px[j],py[j]);
                if (dt[i]+dt[j]+tmp<pmin)
                    pmin=dt[i]+dt[j]+tmp;
            }
        }
    }

    fprintf(fo,"%.6lfn",pmin>max?pmin:max);
    fclose(fi);
    fclose(fo);
    return 0;
}

上次修改时间 2017-02-03

相关日志