[U]2.4.3 Cow Tours

总算是做到了一点点的图论题了~ 意味着后面的难题要来了 还是觉得自己太懒，不愿去花时间，不愿意相信自己。 这个题呢，有点点意思，本来我的代码超时的，随手改了点小东西，没预料到过的竟然过了~ 哇哈哈哈~另类的秒掉了。 解题思路很简单，但是求解过程中

总算是做到了一点点的图论题了~ 意味着后面的难题要来了

还是觉得自己太懒，不愿去花时间，不愿意相信自己本文来源gaodai#ma#com搞@@代~&码*网2。

这个题呢，有点点意思，本来我的代码超时的，随手改了点小东西，没预料到过的竟然过了~ 哇哈哈哈~另类的秒掉了。

解题思路很简单，但是求解过程中会绕很多圈子，有点头疼。

枚举不在一个联通图中的两个点，做边连接它们，在根据题中的定义，求出农场的直径，再通过寻找农场直径中最大值的最小值。这里佷绕！！！

Code：

/*ID:sevenst4LANG:C++PROG:cowtour*/#include#include#define INF 1111111using namespace std;struct node{ 	   double x,y;}p[160];int n;double dis[160][160];double max( double a,double b ){ return a>b?a:b; }double min( double a,double b ){ return a<b?a:b; }double dist( int i,int j ){ 	   return sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) );}double gmdis( int a ){ 	   double ret=0; 	   for( int i=1;idis[a][i]?ret:dis[a][i];       return ret;}double getall(){ 	   double ret=0; 	   for( int i=1;i<=n;i++ )	   for( int j=1;j<=n;j++ )	   		if( i!=j && dis[i][j]!=INF ) 	   	   		ret=max(ret,dis[i][j]);	   return ret;}int main(){ 	freopen( "cowtour.in","r",stdin ); 	freopen( "cowtour.out","w",stdout ); 	scanf( "%d",&n ); 		for( int i=1;i<=n;i++ ) 		 scanf( "%lf %lf",&p[i].x,&p[i].y );		for( int i=0;i<=n;i++ )	for( int j=0;j<=n;j++ )		 dis[i][j]=INF;		char line[160];	for( int i=1;i<=n;i++ )	{	 	 scanf( "%s",&line );	 	 for( int j=0;j<n;j++ )	 	 	  if( line[j]=='1' )			   	  dis[i][j+1]=dist(i,j+1);    }        for( int k=1;k<=n;k++ )    for( int i=1;i<=n;i++ )    for( int j=1;jdis[i][k]+dis[k][j] )    	 	 dis[i][j]=dis[i][k]+dis[k][j];        double ans=INF;    for( int i=1;i<=n;i++ )    for( int j=1;jans )		  	 	 continue;		  	 ans=min( max( getall(),m ),ans );  	     }  	     	printf( "%lf\n",ans );	 	return 0;}

喜欢 (0)赏

[搞代码]

分享 (0)