Cod sursa(job #2798574)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:16:12
Problema Adapost Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.27 kb
#include <stdio.h>
#include <math.h>

#define maxn 1000
#define eps 0.000001
#define maxval 100000

int n,l;
int used[maxn],mark[maxn],grad[maxn],found;
int c[maxn][maxn],f[maxn][maxn],a[maxn*maxn],draw,sol,from[maxn],st[maxn*maxn],h[maxn],poz[maxn];
double d[maxn*maxn],p[maxn],q[maxn],r[maxn],s[maxn],cost[maxn][maxn],ct[maxn],sum,last[maxn];

void citire()
{
    freopen("adapost.in","r",stdin);

    int i;
    scanf("%d",&n);

	for (i=1;i<=n;i++) scanf("%lf%lf",&p[i],&q[i]);

    for (i=1;i<=n;i++) scanf("%lf%lf",&r[i],&s[i]);

}

int part(int p,int r)
{
    int i=p-1,j;
    double aux;

    for (j=p;j<=r;j++)
      if (d[j]<=d[r])
      {
          i++;
          aux=d[i];
          d[i]=d[j];
          d[j]=aux;
      }

    return i;
}

void quick(int p, int r)
{
    if (p<r)
    {
        int q=part(p,r);
        quick(p,q-1);
        quick(q+1,r);
    }
}

double dist(double a,double b,double c,double d)
{
    return sqrt((a-b)*(a-b)+(c-d)*(c-d));
}

void build(double x)
{
     int i,j;
     grad[1]=1;
     for (i=1;i<=n;i++)
     {
         grad[i+1]=grad[i];
         for (j=1;j<=n;j++)
		   if (dist(p[i],r[j],q[i],s[j])<=x+eps)
           {
               a[grad[i+1]]=j;
               grad[i+1]++;
           }
     }
}

int DFS(int nod)
{
	 if (nod==-1) return 1;
	 if (used[nod]==draw) return 0;

     int i;
     used[nod]=draw;
	 for (i=grad[nod];i<grad[nod+1];i++)
       if (DFS(mark[a[i]]))
       {
		  mark[a[i]]=nod;
          return 1;
       }

     return 0;
}

int cuplaj()
{
    int rez=0,i;

    draw=1;
    for (i=1;i<=n;i++)
    {
		mark[i]=-1;
        used[i]=0;
    }

    for (i=1;i<=n;i++)
    {
        rez=rez+DFS(i);
        draw++;
    }

    return rez;
}

void pop(int x)
{
     int aux;
     while ((x/2>1) && (ct[h[x/2]]>ct[h[x]]))
     {
           aux=h[x];
           h[x]=h[x/2];
           h[x/2]=aux;
           poz[h[x]]=x;
           poz[h[x/2]]=x/2;
           x=x/2;
     }
}

void push(int x)
{
     int aux,y=0;

     while (x!=y)
     {
           y=x;
           if ((y*2<=l) && (ct[h[y*2]]<ct[h[x]])) x=y*2;
           if ((y*2+1<=l) && (ct[h[y*2+1]]<ct[h[x]])) x=y*2+1;

           aux=h[x];
           h[x]=h[y];
           h[y]=aux;
           poz[h[x]]=x;
           poz[h[y]]=y;
     }
}

void Bellman(int nod)
{
	 int i=1,j,min;

	 for (i=1;i<=n*2+1;i++)
	 {
		ct[i]=maxval;
		from[i]=-1;
		used[i]=0;
	 }

     used[0]=1;
	 l=1;
	 i=1;
	 st[l]=nod;
	 from[0]=-2;

	 while (l>0)
     {
        for (j=grad[h[1]];j<grad[h[1]+1];j++)
          if ((c[h[1]][a[j]]-f[h[1]][a[j]]>0) && (ct[h[1]]+cost[h[1]][a[j]]<ct[a[j]]))
	  	  {
               ct[a[j]]=ct[h[1]]+cost[h[1]][a[j]];
               from[a[j]]=h[1];
               if (!used[a[j]])
               {
                    l++;
                    used[a[j]]=1;
                    h[l]=a[j];
                    poz[h[l]]=l;
                    pop(l);
               }
               else pop(poz[a[j]]);
          }
        used[h[1]]=0;
        poz[h[1]]=0;
        h[1]=h[l];
        h[l]=0;
        p[h[1]]=1;
        l--;
        if (l>1) push(1);
      }

     if (from[n*2+1]!=-1)
     {
		  found=1;
          i=2*n+1;
          min=maxval;

          while (from[i]!=-2)
          {
                if ((c[from[i]][i]-f[from[i]][i]<min)) min=c[from[i]][i]-f[from[i]][i];
                i=from[i];
          }

          i=n*2+1;
          while (from[i]!=-2)
          {
                f[from[i]][i]=f[from[i]][i]+min;
                f[i][from[i]]=-f[from[i]][i];
                i=from[i];
          }
          sum=sum+ct[2*n+1];
     }
}

void rezolva()
{
	int i,j,front,middle,back;
	l=0;

	for (i=1;i<=n;i++)
	  for (j=1;j<=n;j++)
	  {
		l++;
		d[l]=dist(p[i],r[j],q[i],s[j]);

	  }

	quick(1,l);

	front=1;
	back=l;

    while (front<=back)
    {
        middle=(front+back)/2;

        build(d[middle]);

		if (cuplaj()==n)
		{
           sol=middle;
           back=middle-1;
        }
        else front=middle+1;
    }

    double aux;

    grad[0]=1;
    grad[1]=1;

    for (i=1;i<=n;i++)
    {
        c[0][i]=1;
        a[grad[1]]=i;
        grad[1]++;
    }

    for (i=1;i<=n;i++)
    {
      grad[i+1]=grad[i];
      for (j=1;j<=n;j++)
      {
        aux=dist(p[i],r[j],q[i],s[j]);
        if (aux<=d[sol]+eps)
        {
            a[grad[i+1]]=n+j;
            grad[i+1]++;
            c[i][n+j]=1;
            cost[i][n+j]=aux;
            cost[n+j][i]=-aux;
		}
	  }
	  a[grad[i+1]]=0;
	  grad[i+1]++;
	}

	for (i=n+1;i<=n*2;i++)
	{
		grad[i+1]=grad[i];
		for (j=1;j<=n;j++)
		{
		   aux=dist(p[j],r[i-n],q[j],s[i-n]);
		   if (aux<=d[sol]+eps)
		   {
			  a[grad[i+1]]=j;
			  grad[i+1]++;
		   }
		}
		c[i][2*n+1]=1;
		a[grad[i+1]]=n*2+1;
		grad[i+1]++;
	}

	grad[2*n+2]=grad[2*n+1];
	for (i=1;i<=n;i++)
	{
	  a[grad[2*n+2]]=n+i;
	  grad[n*2+2]++;
	}


	found=1;
	while (found)
    {
          found=0;
          Bellman(0);
    }

}

void afisare()
{
	 freopen("adapost.out","w",stdout);

     printf("%.5lf %.5lf\n",d[sol],sum);
}

int main()
{
	citire();
    rezolva();
    afisare();

    return 0;
}