Cod sursa(job #203387)

Utilizator VmanDuta Vlad Vman Data 15 august 2008 23:12:56
Problema Adapost Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.87 kb
using namespace std;
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>

#define Nmax 402

struct punct { float x,y; };
struct distanta { float v; int a,b; };

int N;
int i,j,maxim;
float total;
vector<int> G[2*Nmax]; //graf
char R[2*Nmax][2*Nmax]; //capacitati
punct S[Nmax],A[Nmax];
int T[2*Nmax], Q[30*Nmax];
char is[2*Nmax];
float D[2*Nmax];

distanta dist[Nmax*Nmax];
int nrd;

void citire()
{
 float d;
 
 freopen("adapost.in","r",stdin);
 scanf("%d",&N);
 for (i=1; i<=N; ++i)
     scanf("%f %f",&S[i].x,&S[i].y);
 for (i=1; i<=N; ++i)
     scanf("%f %f",&A[i].x,&A[i].y);
 for (i=1; i<=N; ++i)
     for (j=1; j<=N; ++j)
         {
          d = 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) );
          dist[++nrd].v = d;
          dist[nrd].a = i;
          dist[nrd].b = N+j;
         }
}

int cmp(const distanta &A, const distanta &B)
{
 return A.v < B.v;
}

void build()
{
 //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)
         R[i][j] = 1, 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;
 vector<int>::iterator it;
 
 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] = 999999, is[i] = 0;

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

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

        if (nod<=N)
           for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
               if (R[nod][dist[*it].b] && D[nod] + dist[*it].v < D[dist[*it].b])
                  {
                   D[dist[*it].b] = D[nod] + dist[*it].v;
                   T[dist[*it].b] = nod;
                   if (!is[dist[*it].b]) Q[++dr] = dist[*it].b, is[Q[dr]]=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 (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
               if (R[nod][dist[*it].a] && D[nod] - dist[*it].v < D[dist[*it].a])
                  {
                   D[dist[*it].a] = D[nod] - dist[*it].v;
                   T[dist[*it].a] = nod;
                   if (!is[dist[*it].a]) Q[++dr] = dist[*it].a, is[Q[dr]]=1;
                  }
          }

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

int bfs()
{
 int nod, st=1, dr=0;
 vector<int>::iterator it;
 
 memset(T,0,sizeof(T));

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

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

        if (nod<=N)
           for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
               if (R[nod][dist[*it].b] && !T[dist[*it].b])
                  {
                   Q[++dr] = dist[*it].b;
                   T[Q[dr]] = nod;
                  }

        if (nod>N)
          {
           if (R[nod][2*N+1])
              { T[2*N+1] = nod; return nod; }
                
           for (it=G[nod].begin(); it<G[nod].end() && *it<=maxim; ++it)
               if (R[nod][dist[*it].a] && !T[dist[*it].a])
                  {
                   Q[++dr] = dist[*it].a;                                      
                   T[Q[dr]] = nod;
                  }
          }
        ++st;
       }
       
 return T[2*N+1];
}

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

void match2()
{
 int nod;
 
 total = 0;
 
 while ( bellman() )
       {
        nod = 2*N+1;
        total += D[nod];
        nod = 2*N+1;
        while ( nod )
              {
               R[nod][T[nod]]=1, R[T[nod]][nod]=0;
               nod = T[nod];
              }
       }
}

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

 maxim=m+1;
 build();
 match2();
 freopen("adapost.out","w",stdout);
 printf("%.5f %.5f\n", dist[maxim].v, total);
 fclose(stdout);
}

int main()
{
 citire();

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

 //construieste grafu
 for (i=1; i<=nrd; ++i)
     {
      G[ dist[i].a ].push_back(i);
      G[ dist[i].b ].push_back(i);
     }

 cauta();
 
 return 0;
}