Cod sursa(job #46821)

Utilizator MARCELMIHALCEA MARICEL MARCEL Data 2 aprilie 2007 23:56:41
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb


#include<stdio.h>
#include<math.h>

#define Nmax 101
#define INF 100000000

float max(float x,float y) { return  x < y ? y : x  ; }

int prec[Nmax],n,m;

 struct muchie{
 int c;
 float d; }a[Nmax][Nmax];

struct punct{
 float x,y; } g[Nmax],h[Nmax];

 float dist( punct A, punct B)
  {
  return (sqrt)( (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y) );
  }


int Bellman()
 {

 int i,j,k;
 float d[Nmax];

 for(i=1;i<=m+n+1;i++)
  d[i]=INF;

 for(i=0;i<=m;i++)
  if( a[0][i].c )
   {
   d[i]=0;
   prec[i]=0;
   }

  prec[0]=0;

 for( k=1;k<=n+m;k++ )
  for( i=0;i<=n+m;i++ )
   for(j=1;j<=n+m+1;j++)
	if( a[i][j].c )
	  if( d[j] > d[i]+a[i][j].d )
		 {
		 d[j] = d[i]+a[i][j].d ;
		 prec[j]=i;
		 }


   return 1;
 }


int main()
{
int nrtest,N,k,i,j,nod,pasi=0;
float F,Sol=0;


freopen("gopher.in","r",stdin);
freopen("gopher.out","w",stdout);


for(scanf("%d",&N),nrtest=1; nrtest<=N ; nrtest++ )
 {

 scanf("%d%d%d",&m,&n,&k);

 for(i=1;i<=m;i++)
  scanf("%f%f",&g[i].x,&g[i].y);

 for(i=1;i<=n;i++)
  scanf("%f%f",&h[i].x,&h[i].y);

  if( m-k > n )
   {
	printf("Case #%d:\n",nrtest);
	printf("Too bad.\n\n");
   continue;
   }

  for(i=1;i<=m;i++) for(j=0;j<=n;j++) a[i][j].d=a[i][j].c=0;

  for(i=1;i<=m;i++)
   for(j=1;j<=n;j++)
	{
	a[i][j+m].d=dist(g[i],h[j]);
	a[i][j+m].c=1;
	}

  for( i=1;i<=m;i++)
   {
   a[0][i].d=0;
   a[0][i].c=1;
   }

 for( i=m+1; i<=m+n; i++)
   {
   a[i][m+n+1].d=0;
   a[i][m+n+1].c=1;
   }


   pasi=1;

   while( pasi <= m-k && Bellman() )
	{
	pasi ++ ;

	nod=m+n+1;

   F=0;

	while( nod != prec[nod] )
	{
	if(a[prec[nod]][nod].d>0)
	 F=max(F,a[prec[nod]][nod].d);

	a[prec[nod]][nod].c= 0;
	a[nod][prec[nod]].c= 1;

	a[nod][prec[nod]].d=-a[prec[nod]][nod].d;
	a[prec[nod]][nod].d=0;

	nod=prec[nod];
	}

	Sol=max(Sol,F);
	}


	printf("Case #%d:\n",nrtest);

	if( fabs(Sol*1e3 - floor(Sol*1e3) - 0.5) > 1e-2 )
	 printf("%.3f\n",Sol);
	 else
	 printf("Too bad.\n");

	 if( nrtest<N ) printf("\n");

 }


 return 0;
 }