Cod sursa(job #203354)

Utilizator VmanDuta Vlad Vman Data 15 august 2008 18:17:16
Problema Adapost Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.25 kb
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

#define Nmax 512

struct punct { double x,y; };

int N;
int i,j;
double total;
double C[2*Nmax][2*Nmax]; //costuri
char R[2*Nmax][2*Nmax]; //capacitati
punct S[Nmax],A[Nmax];
int T[2*Nmax], Q[20*Nmax];
char is[2*Nmax];
double D[2*Nmax];

double dist[Nmax*Nmax];
int nrd;

void citire()
{
 freopen("adapost.in","r",stdin);
 scanf("%d",&N);
 for (i=1; i<=N; ++i)
     scanf("%lf %lf",&S[i].x,&S[i].y);
 for (i=1; i<=N; ++i)
     scanf("%lf %lf",&A[i].x,&A[i].y);
 for (i=1; i<=N; ++i)
     for (j=1; j<=N; ++j)
         {
          C[i][N+j] = sqrt( (S[i].x-A[j].x)*(S[i].x-A[j].x) + (S[i].y-A[j].y)*(S[i].y-A[j].y) );
          C[N+j][i] = - C[i][N+j];
          dist[++nrd] = C[i][N+j];
         }
}

void build(double maxim)
{
 //sursa la soldat
 for (i=1; i<=N; ++i)
      R[0][i] = 1, R[i][0] = 0;
 //soldat la adapost
 for (i=1; i<=N; ++i)
     for (j=N+1; j<=2*N; ++j)
       if (C[i][j] <= maxim)
         R[i][j] = 1, R[j][i] = 0;         
        else R[i][j] = R[j][i] = 0; 
 //adapost la destinatie
 for (i=N+1; i<=2*N; ++i)
     R[i][2*N+1] = 1, R[2*N+1][i] = 0; 
}

int bellman()
{
 int nod, st=1, dr=0;
 
 T[2*N+1] = 0;

 for (i=1; i<=N; ++i)
        if (R[0][i])
                {
                 Q[++dr] = i;
                 is[i] = 1;
                 D[i] = T[i] =0;
                }
        else D[i] = 9999999, is[i] = 0;

 for (i=N+1; i<=2*N+1; ++i)
         D[i] = 99999999, is[i] = 0;

 while (st<=dr)
       {
        nod = Q[st];

        if (nod<=N)
           for (i=N+1; i<=2*N; ++i)
               if (R[nod][i] && D[nod] + C[nod][i] < D[i])
                  {
                   D[i] = D[nod] + C[nod][i];
                   T[i] = nod;
                   if (!is[i]) Q[++dr] = i, is[i]=1;
                  }

        if (nod>N)
          {
           if (R[nod][2*N+1] && D[nod]<D[2*N+1])
                D[2*N+1] = D[nod], T[2*N+1] = nod;
                
           for (i=1; i<=N; ++i)
               if (R[nod][i] && D[nod] + C[nod][i] < D[i])
                  {
                   D[i] = D[nod] + C[nod][i];
                   T[i] = nod;
                   if (!is[i]) Q[++dr] = i, is[i]=1;
                  }
          }

        ++st;
        is[nod] = 0;
       }
       
 return T[2*N+1];
}

int match()
{
 int nr = 0, nod;
 
 total = 0;
 
 while ( bellman() )
       {
        ++nr;
        nod = 2*N+1;
        while ( nod )
              {
               total += C[T[nod]][nod];
               nod = T[nod];
              }
        nod = 2*N+1;
        while ( nod )
              {
               R[nod][T[nod]]=1, R[T[nod]][nod]=0;
               nod = T[nod];
              }
       }
 return nr;
}

void cauta()
{
 int m=0, p=1;
 
 while ( (p<<1) <= nrd ) p <<= 1;
 
 while (p)
       {
        build(dist[m+p]);
        if (match() < N) m+=p;
        p >>= 1;
        while (m+p > nrd) p>>=1;
       }

 build(dist[m+1]);
 match();
 freopen("adapost.out","w",stdout);
 printf("%.5lf %.5lf\n", dist[m+1], total);
 fclose(stdout);
}

int main()
{
 citire();

 sort(dist+1, dist+nrd+1);

 cauta();
 
 return 0;
}