Pagini recente » Cod sursa (job #2309678) | Cod sursa (job #1772288) | Cod sursa (job #2514258) | Cod sursa (job #185251) | Cod sursa (job #46821)
Cod sursa(job #46821)
#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;
}