cowtour.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: cowtour
LANG: C++
*/
#include <iostream>
#include <cmath>
using namespace std;

#define MAXARRAY2 151

//--------封装2维数组---------
class _2int
{
public:
	double (*num)[MAXARRAY2];
	int u1,u2;
	_2int(int u1,int u2,int begin)
	{
		num = new double[u1][MAXARRAY2];
		memset(num,begin,sizeof(num));
	}
};
//----------------------------

//---------矩阵---------------
class _Matrix
{
public:
	double (*num)[MAXARRAY2];
	int Width,Height;
	_Matrix(const int width,const int height)
	{
		num = new double[width][MAXARRAY2];
		Width = width;Height = height;
		for(int a=0;a<width;a++)
			for(int b=0;b<height;b++)
				num[a][b]=0;
	}
};
//----------------------------

//----------加权图------------
class _WeightG
{
public:
	_Matrix *num;
	int Width,Height;
	_WeightG(const int vertexNum)
	{
		num = new _Matrix(vertexNum,vertexNum);
		Width = vertexNum;
		Height = vertexNum;
	}
};
//----------------------------

//------------Floyd------------
//Use:图中任意两点间最短距离
//O(n^3)
void Root(int p,int q,int *k,_2int *Path,int *Line)
{
	if (Path->num[p][q]>0)
	{
		Root(p,Path->num[p][q],k,Path,Line);
		Root(Path->num[p][q],q,k,Path,Line);
	}
	else 
	{
		Line[(*k)]=q;
		(*k)++;
	}
}

_2int* Floyd(_WeightG *thisG)
{
	int p,q,k,m;
	int Vertex = thisG->Height;int *Line;
	_2int *answer;
	answer = new _2int(Vertex,Vertex,0);
	for(p=0;p<Vertex;p++)
		for(q=0;q<Vertex;q++)
			answer->num[p][q]=thisG->num->num[p][q];
	for(k=0;k<Vertex;k++)
		for(p=0;p<Vertex;p++)
			if (answer->num[p][k]>0)
				for(q=0;q<Vertex;q++)
					if (answer->num[k][q]>0)
						if (((answer->num[p][q]>answer->num[p][k]+answer->num[k][q])||(answer->num[p][q]==0))&&(p!=q))
							answer->num[p][q]=answer->num[p][k]+answer->num[k][q];
	return answer;
}


//---------End Floyd----------
int N;

int x[151], y[151];

#define MAX(A,B) (A>B?A:B)
#define MIN(A,B) (A<B?A:B)

int pasturenum=0;
int pastureLe[151];
int pastureVert[151][151];
double maxL[151]={0};
double maxSL[151]={0};
bool hash[151];
_2int *answer;
#define Dis(A,B) (sqrt((double)((x[A]-x[B])*(x[A]-x[B])+(y[A]-y[B])*(y[A]-y[B]))))
double maxlength(int set1,int set2)
{
	double tanswer=999999.0;
	for(int a=1;a<=pastureLe[set1];a++)
		for(int b=1;b<=pastureLe[set2];b++)
			tanswer=MIN(tanswer,MAX(MAX(maxSL[set1],maxSL[set2]),maxL[pastureVert[set1][a]]+maxL[pastureVert[set2][b]]+Dis(pastureVert[set1][a],pastureVert[set2][b])));
	return tanswer;
}

int main()
{
	freopen("cowtour.in","r",stdin);
	freopen("cowtour.out","w",stdout);
	scanf("%d",&N);
	_WeightG thisG(N);
	
	int t;char ch;
	for(int a=1;a<=N;a++)
		scanf("%d%d",&x[a],&y[a]);
	for(int a=1;a<=N;a++)
		for(int b=1;b<=N;b++)
		{
			scanf("%c",&ch);
			if(ch=='\n') scanf("%c",&ch);
			if(ch=='1')
			{thisG.num->num[a-1][b-1]=Dis(a,b);
			 thisG.num->num[b-1][a-1]=thisG.num->num[a-1][b-1];}
		}
	answer = Floyd(&thisG);
	
	for(int a=1;a<=N;a++)
		if(!hash[a])
		{
			pasturenum++;
			pastureLe[pasturenum]=1;
			pastureVert[pasturenum][1]=a;
			hash[a]=true;
			for(int b=1;b<=N;b++)
				if(answer->num[a-1][b-1]>0)
				{
					hash[b]=true;
					pastureVert[pasturenum][++pastureLe[pasturenum]]=b;
				}
		}
	for(int a=1;a<=pasturenum;a++)
		for(int b=1;b<=pastureLe[a];b++)
			for(int c=1;c<=pastureLe[a];c++)
			{
				maxL[pastureVert[a][b]]=MAX(maxL[pastureVert[a][b]],answer->num[pastureVert[a][b]-1][pastureVert[a][c]-1]);
				maxSL[a]=MAX(maxSL[a],maxL[pastureVert[a][b]]);
			}
	double tanswer=999999999.0;
	for(int a=1;a<pasturenum;a++)
		for(int b=a+1;b<=pasturenum;b++)
			tanswer = MIN(tanswer,maxlength(a,b));
	printf("%.6lf\n",tanswer);
	return 0;
}