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;
}

相關日誌