Cod sursa(job #71006)

Utilizator moga_florianFlorian MOGA moga_florian Data 8 iulie 2007 21:13:30
Problema Adapost Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.31 kb
using namespace std;
#include<fstream>
#include<stdio.h>
#include<math.h>
#define Nmax 500
#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 heap[2*Nmax],nh,ph[2*Nmax],ant[2*Nmax];
ifstream fin("adapost.in");
FILE *fout=fopen("adapost.out","w");

double flow(double Vmax)
{
int i,j;
   
//initializare
for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)  
     {
     cost[j+N][i]=0.0;
     cap[j+N][i]=0;
     
     if(init[i][j] <= Vmax)
        {
        cost[i][j+N]=init[i][j];
        cap[i][j+N]=1;           
        }
     else
        {
        cost[i][j+N]=0.0;
        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,aux,ori=0;
double F=0.0;

while(1)
{        
nh=2*N+2;
for(i=0;i<=2*N+1;i++) 
   {
   flux[i]=inf;
   heap[i+1]=i;
   ph[i]=i+1;   
   }
flux[0]=0.0;

while(heap[1] != dest && flux[heap[1]] < inf)
    {
    X=heap[1];
    //intersc 1 cu nh
    aux=heap[1];
    heap[1]=heap[nh];
    heap[nh]=aux;
    ph[heap[1]]=1;
    ph[heap[nh]]=nh;
    nh--;
    
    i=1;
    while(1)
      {
      j=i<<1;
      if(j>nh) break;
      if(j+1<=nh && flux[heap[j+1]] < flux[heap[j]]) j++;
      if(flux[heap[i]] <= flux[heap[j]]) break;
      
      aux=heap[i];
      heap[i]=heap[j];
      heap[j]=aux;
      ph[heap[i]]=i;
      ph[heap[j]]=j;
      i=j;      
      }
    
    if(X<=N && X>0)
       {
       for(i=N+1;i<=2*N;i++)
          if(cap[X][i] && flux[i] > flux[X] + cost[X][i])
              {
              flux[i]=flux[X]+cost[X][i];
              ant[i]=X;
              
              //refacere heap
              j=ph[i];
              while(j/2 && flux[heap[j/2]] > flux[heap[j]] )
                  {
                  aux=heap[j/2];
                  heap[j/2]=heap[j];
                  heap[j]=aux;
                  ph[heap[j/2]]=j/2;
                  ph[heap[j]]=j;
                  
                  j>>=1;      
                  }         
              }               
       }
    else
       {
       for(i=1;i<=N;i++)
          if(cap[X][i] && flux[i] > flux[X] + cost[X][i])
              {
              flux[i]=flux[X]+cost[X][i];
              ant[i]=X;
              
              //refacere heap
              j=ph[i];
              while(j/2 && flux[heap[j/2]] > flux[heap[j]] )
                  {
                  aux=heap[j/2];
                  heap[j/2]=heap[j];
                  heap[j]=aux;
                  ph[heap[j/2]]=j/2;
                  ph[heap[j]]=j;
                  
                  j>>=1;      
                  }         
              }
              
       if(cap[X][dest] && flux[dest]> flux[X] + cost[X][dest])
              {
              flux[dest]=flux[X]+cost[X][dest];
              ant[dest]=X;
              
              //refacere heap
              j=ph[dest];
              while(j/2 && flux[heap[j/2]] > flux[heap[j]] )
                  {
                  aux=heap[j/2];
                  heap[j/2]=heap[j];
                  heap[j]=aux;
                  ph[heap[j/2]]=j/2;
                  ph[heap[j]]=j;
                  
                  j>>=1;      
                  }                                
              }
       }
    
    
    }

if(flux[heap[1]] == 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;
   cost[i][ant[i]] = -cost[ant[i]][i];
   cost[ant[i]][i]=0.0;
   
   i=ant[i];       
   }
   
F+=flux[dest];   
ori++;
}
  
}

int main()
{
int i,j,k;
double dx,dy,val,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];
     }
     
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;
        
        j/=2;
        }              
     }
     
i=N*N;
while(i>1)
 {
 aux=dist[1];
 dist[1]=dist[i];
 dist[i]=aux;
 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;
   j=k;      
   }         
 }

int li,lf,mij;
double distMin,totalMin;
li=1;lf=N*N;


for(li=1;1;li++)
    {
    val=flow(dist[li]);
    if(val >= 0.0)
        {
        distMin=dist[li];
        totalMin=val;
        break;      
        }              
    }

/*
while(li<=lf)
  {
  mij=(li+lf)>>1;
  val=flow(dist[mij]);
  if( val >= 0.0 )
      {
      distMin= dist[mij];
      totalMin= val;
      
      lf=mij-1;             
      }
  else
      li=mij+1;  
  }
*/
  
fprintf(fout,"%f %f\n",distMin,totalMin);
fin.close();
fclose(fout);
return 0;    
}