Home > Old Blog Posts > USACO 2.4.3 Cow Tours

USACO 2.4.3 Cow Tours


先用floyd过一遍,取任两个牧区中的点i,j,maxx[i]为从i点出发的最远距离,maxl为maxx中的最大值,则直径为 max(maxx[i]+maxx[j]+dis(i,j),maxl),但在实现上可先求出最短的maxx[i]+maxx[j]+dis(i,j),再和 maxl比较取最大值为答案。

代码:

/*
ID: dementr1
PROG: cowtour
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<stdio.h>
#include”math.h”
using namespace std;
struct xy
{
long double x,y;
}  pix[200];
long double dis[200][200],a[200][200];
int N;
long double ptdist(xy a, xy b)
{
return sqrt((long double)(b.x-a.x)*(b.x-a.x)+(long double)(b.y-a.y)*(b.y-a.y));
}
void init()
{
string s;
int i,j;
ifstream fin(“cowtour.in”);
fin>>N;
for(i=0;i<N;i++)
fin>>pix[i].x>>pix[i].y;
for(i=0;i<N;i++)
{
fin>>s;
for(j=0;j<N;j++)
{
if(s[j]-‘0’==1)
a[i][j]=ptdist(pix[i],pix[j]);
else a[i][j]=100000;
}
}
fin.close();
}
void floyd()
{
int i,j,k;
double mx[200]={},maxx=0,min=100000;
for(k=0;k<N;k++)
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if((i!=k&&i!=j&&k!=j)&&(a[i][k]+a[k][j]<a[i][j])) a[i][j]=a[i][k]+a[k][j];
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if(a[i][j]!=100000&&a[i][j]>mx[i]) mx[i]=a[i][j];
if(mx[i]>maxx) maxx=mx[i];
}
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i!=j&&a[i][j]==100000)
if(mx[i]+mx[j]+ptdist(pix[i],pix[j])<min) min=mx[i]+mx[j]+ptdist(pix[i],pix[j]);
FILE *fout=fopen(“cowtour.out”,”w”);
fprintf(fout,”%lf\n”,max(maxx,min));
}
int main()
{
init();
floyd();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: