USACO-Chapter2.rar_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; }