Cod sursa(job #71071)

Utilizator moga_florianFlorian MOGA moga_florian Data 9 iulie 2007 09:59:38
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.42 kb
using namespace std;
#include<fstream>
#include<stdio.h>
#include<math.h>
#define Nmax 405
#define inf 100000000.0

int N;
double cxad[Nmax],cyad[Nmax],cxsol[Nmax],cysol[Nmax],dist[Nmax*Nmax],init[Nmax][Nmax];
double cost[2*Nmax][2*Nmax],flux[2*Nmax];
char cap[2*Nmax][2*Nmax];
int q[Nmax*Nmax],ant[Nmax],soldat[2*Nmax];
char inq[2*Nmax];
int vec[Nmax][Nmax],nvec[Nmax],bfs[2*Nmax];
int x[Nmax*Nmax],y[Nmax*Nmax];

ifstream fin("adapost.in");
FILE *fout=fopen("adapost.out","w");

double flow(double Vmax)
{
int i,j;
   
//initializare
memset(inq,0,sizeof inq);
for(i=1;i<=N;i++)
  {
  nvec[i]=0;
  for(j=1;j<=N;j++)  
     {
     cap[j+N][i]=0;
          
     if(init[i][j] <= Vmax)
        {
        vec[i][++nvec[i]]=j+N;
        cost[i][j+N]=init[i][j];
        cost[j+N][i]=-init[i][j];
        cap[i][j+N]=1;           
        }
     else
        cap[i][j+N]=0;                         
     }
  }
     
for(i=1;i<=N;i++)
   {
   cap[0][i]=cap[i+N][2*N+1]=1;
   cap[i][0]=cap[2*N+1][i+N]=0;
   cost[0][i]=cost[i+N][2*N+1]=0.0;              
   cost[i][0]=cost[2*N+1][i+N]=0.0;
   }
     
int X,dest=2*N+1,ori=0,li,lf;
double F=0.0;


while(1)
{        
for(i=1;i<=2*N+1;i++) 
   flux[i]=inf;
flux[0]=0.0;
li=1;lf=1;
q[1]=0;
inq[0]=1;

while(li<=lf)
    {
    X=q[li];
    
    if(X<=N && X>0)
       {
       for(j=1;j<=nvec[X];j++)
          {
          i=vec[X][j];
          if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
              {
              flux[i]=flux[X]+cost[X][i];
              ant[i]=X;
              
              if(!inq[i])
                 {
                 q[++lf]=i;              
                 inq[i]=1;
                 }
              }               
          }
       }
    else
       {
       if(X==0)
        {
        for(i=1;i<=N;i++)
          if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
              {
              flux[i]=flux[X]+cost[X][i];
              ant[i]=X;
              
              if(!inq[i])
               {
               q[++lf]=i;
               inq[i]=1;
               }
              }
        }
       else
       { 
       i=soldat[X];
       if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
              {
              flux[i]=flux[X]+cost[X][i];
              ant[i]=X;
              
              if(!inq[i])
               {
               q[++lf]=i;
               inq[i]=1;
               }
              }              
              
       if(cap[X][dest] && flux[dest]> flux[X] + cost[X][dest])
              {
              flux[dest]=flux[X]+cost[X][dest];
              ant[dest]=X;              
              }
       }       
       
       }
       
    li++;
    inq[X]=0;
    }

if(flux[dest] == inf)
   if(ori==N)
      return F;
   else
      return -1.0;

i=dest;
while(i>0)
   {
   cap[ant[i]][i]=0;
   cap[i][ant[i]]=1;
   if(i>N && ant[i]<=N)
      soldat[i]=ant[i];
   i=ant[i];       
   }
   
F+=flux[dest];   
ori++;
}
}

int simple_flow(int fin)
{    
memset(nvec,0,sizeof nvec);
int i,F=0,li,lf,X,j;
for(i=1;i<=fin;i++) 
   {
   vec[x[i]][ ++nvec[x[i]] ] =y[i];
   cap[x[i]][y[i]]=1;
   cap[y[i]][x[i]]=0;
   }  
for(i=1;i<=N;i++)
   {
   vec[0][++nvec[0]]=i;
   cap[0][i]=1;
   cap[i][0]=0;
   
   cap[i+N][2*N+1]=1;
   cap[2*N+1][i+N]=0;              
   }
   
while(F<N)
  {
  memset(inq,0,sizeof inq);
  li=lf=1;
  bfs[li]=0;
  
  while(li<=lf)
     {
     X=bfs[li];
     if(X<=N && X>0)
       {
       for(j=1;j<=nvec[X];j++)
          {
          i=vec[X][j];
          if(cap[X][i] && !inq[i])
              {
              ant[i]=X;
              bfs[++lf]=i;              
              inq[i]=1;
              }               
          }
       }
    else
       {
       if(X==0)
        {
        for(i=1;i<=N;i++)
          if(cap[X][i] && !inq[i])
              {
              ant[i]=X;
              bfs[++lf]=i;
              inq[i]=1;
              }
        }
       else
        { 
        i=soldat[X];
        if(cap[X][i] && !inq[i])
              {
              ant[i]=X;
              bfs[++lf]=i;
              inq[i]=1;
              }              
              
        if(cap[X][2*N+1])
              {
              ant[2*N+1]=X;              
              inq[2*N+1]=1;
              break;
              }
        }                     
       }
       
     li++;
     }
     
  if(inq[2*N+1]==0) break;

  F++;
  i=2*N+1;
  while(i>0)
     {
     cap[ant[i]][i]=0;
     cap[i][ant[i]]=1;
     if(i>N && ant[i]<=N)
        soldat[i]=ant[i];
     
     i=ant[i];       
     }
  }
  
return F;
}

int main()
{
int i,j,k,auxx;
double dx,dy,aux;

fin>>N;
for(i=1;i<=N;i++)
   fin>>cxsol[i]>>cysol[i];
for(i=1;i<=N;i++)
   fin>>cxad[i]>>cyad[i];
   
k=0;
for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)
     {
     dx=cxsol[i] - cxad[j];
     dy=cysol[i] - cyad[j];
     
     init[i][j]= sqrt(dx*dx + dy*dy);
     
     dist[++k]=init[i][j];
     x[k]=i;
     y[k]=j+N;
     }
     
for(i=1;i<=N*N;i++)
     {
     j=i;
     while(j/2 && dist[j/2] < dist[j]) 
        {
        aux=dist[j/2];
        dist[j/2]=dist[j];
        dist[j]=aux;
        
        auxx=x[j/2];
        x[j/2]=x[j];
        x[j]=auxx;
        
        auxx=y[j/2];
        y[j/2]=y[j];
        y[j]=auxx;
        
        j/=2;
        }              
     }
     
i=N*N;
while(i>1)
 {
 aux=dist[1];
 dist[1]=dist[i];
 dist[i]=aux;
        auxx=x[1];
        x[1]=x[i];
        x[i]=auxx;
        
        auxx=y[1];
        y[1]=y[i];
        y[i]=auxx;
 i--;
 
 j=1;
 while(1)
   {
   k=j*2;
   if(k>i) break;
   if(k+1<=i && dist[k+1] > dist[k]) k++;
   if(dist[j] >= dist[k]) break;
   
   aux=dist[j];
   dist[j]=dist[k];
   dist[k]=aux;
        auxx=x[k];
        x[k]=x[j];
        x[j]=auxx;
        
        auxx=y[k];
        y[k]=y[j];
        y[j]=auxx;

   j=k;      
   }         
 }

int li,lf,mij,ind=0;
li=1;
lf=N*N;

while(li<=lf)
  {
  mij=(li+lf)>>1;

  if( simple_flow(mij) == N )
      {
      ind=mij;
      lf=mij-1;             
      }
  else
      li=mij+1;  
  }

  
fprintf(fout,"%f %f\n",dist[ind],flow(dist[ind]));

fin.close();
fclose(fout);
return 0;    
}