Cod sursa(job #298303)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 aprilie 2009 23:14:17
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <stdio.h>
#include <math.h>
#define N 403

using namespace std;

struct pct
{
     double x,y;
}s[N],s1[N];

double infinit=1000000;
double dist[2*N+2][2*N+2];
double C[N];
double rez,Fl;
int cap[2*N+2][2*N+2];
int tati[2*N+2];
int viz[2*N+2];
int Q[2*N+2];
int inc,sf,n;
int S=0,D;

double distanta(pct a,pct b)
{
     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void citire()
{
     freopen ("adapost.in","r",stdin);
     freopen ("adapost.out","w",stdout);
     scanf ("%d",&n);
     D=2*n+1;
     for (int i=1;i<=n;i++)
          scanf ("%lf %lf",&s[i].x,&s[i].y);

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

     for (int i=1;i<=n;i++)
     {
          cap[0][i]=1;
          for (int j=1;j<=n;j++)
          {
               cap[i][j+n]=1;
               dist[i][j+n]=distanta(s[i],s1[j]);
               dist[j+n][i]=-dist[i][j+n];
               cap[j+n][D]=1;
          }
     }
}

void bell()
{
     for (int i=1;i<=2*n+1;i++)
          C[i]=infinit;
     int nod;
     double cc;
     C[S]=0;
     inc=0;
     sf=1;
     Q[0]=S;
     viz[S]=1;
     while (inc<sf)
     {
          nod=Q[inc++];
          viz[nod]=0;
          cc=C[nod];
          for (int i=1;i<=2*n+1;i++)
               if (cap[nod][i] && C[i]>C[nod]+dist[nod][i])
               {
                    tati[i]=nod;
                    C[i]=C[nod]+dist[nod][i];
                    if (!viz[i])
                    {
                         viz[i]=1;
                         Q[sf++]=i;
                    }
               }
     }
}

int mini(int a,int  b)
{
     return a>b?b:a;
}


void calc()
{
     Fl=-1;
     int poz;
     int flux;
     bell();
     while (C[D]!=infinit)
     {
          poz=D;
          flux=2;
          while (poz!=S)
          {
               flux=mini(flux,cap[tati[poz]][poz]);
               poz=tati[poz];
          }

          poz=D;
          while (poz!=S)
          {
               cap[poz][tati[poz]]+=flux;
               cap[tati[poz]][poz]-=flux;
               poz=tati[poz];
          }
          rez+=C[D];
          bell();
     }
}

int main ()
{
     citire();
     calc();
     for (int i=1;i<=n;i++)
          for (int j=1;j<=n;j++)
               if (cap[i][j+n]==0 && dist[i][j+n]>Fl)
                    Fl=dist[i][j+n];
     printf("%lf %lf\n",Fl,rez);
     return 0;
}