Cod sursa(job #2798585)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:31:02
Problema Adapost Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define file_in "adapost.in"
#define file_out "adapost.out"

#define nmax 1010

int l[nmax*nmax];
int r[nmax*nmax];
int viz[nmax*nmax];
int viz1[nmax*nmax];
vector<int> G[nmax*nmax];
vector<pair<int,double > > g[nmax*nmax];
struct pozitie{
	int i,j;
	double d;
}p[nmax*nmax];
struct q{
double x,y;
}a[nmax*nmax],b[nmax*nmax];
int N,nr,dest,x,y,tata[nmax*nmax];
int C[nmax][nmax];
int F[nmax][nmax];
double cost[nmax*nmax];

double dist(double x1, double y1, double x2, double y2){

	return sqrt((y1-y2)*(y1-y2)+(x1-x2)*(x1-x2));
}

bool cmp(const pozitie &a,const pozitie &b){

	return a.d<b.d;
}

struct comp
{
	bool operator()(int i,int j)
	{
		return cost[i]>cost[j];
	}
};
priority_queue<int,vector<int>,comp> q;



int cupleaza(int nod)
{
    if (viz[nod])
         return 0;
     viz[nod]=1;

     vector<int> :: iterator it;

     for (it=G[nod].begin();it!=G[nod].end();++it)
          if (!r[*it])
          {
              l[nod]=(*it);
              r[*it]=nod;
              return 1;
          }
      for (it=G[nod].begin();it!=G[nod].end();++it)
          if (cupleaza(r[*it]))
          {
              l[nod]=(*it);
              r[*it]=nod;
              return 1;
          }

          return 0;

}

void constr_graf(double nod){

	int i;

	for (i=1;i<=N;++i){
		 G[i].clear();
		 l[i]=r[i]=0;
	}

	for (i=1;i<=nr && p[i].d<=nod;++i)
		 G[p[i].i].push_back(p[i].j);
}



int bun(double nod){

	int ok,ans,i;

	constr_graf(nod);

	ok=1;
    ans=0;

    while(ok)
    {
        for (i=1;i<=N;++i) viz[i]=0;
        ok=0;
        for (i=1;i<=N;++i)
             if (!l[i] && cupleaza(i))
             {
					 ans++;
                     ok=1;
			 }
    }

	if (ans!=N)
        return 0;

	return 1;
}

#define inf 0x3f3f3f3f

int dijkstra()
{
    vector< pair <int,double> > :: iterator it;
	int i,nod;
	for(i=1;i<=dest;++i) cost[i]=inf;
	q.push(0);
	cost[0]=0;
	while(!q.empty())
	{
		nod=q.top();
		viz1[nod]=0;
		q.pop();
		for(it=g[nod].begin();it!=g[nod].end();++it)
			if(C[nod][(it->first)]-F[nod][(it->first)]>0 && cost[(it->first)]>cost[nod]+(it->second))
			{
				cost[(it->first)]=cost[nod]+(it->second);
                tata[(it->first)]=nod;
				if(viz1[(it->first)]!=1){
					q.push(it->first);
					viz1[it->first]=1;
				}
			}
	}
	if(cost[dest]<inf)
        return 1;
    return 0;
}



int main(){

	int i,j,ls,ld,mij;

	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);

	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 scanf("%lf %lf", &a[i].x, &a[i].y);
	for (i=1;i<=N;++i)
		 scanf("%lf %lf", &b[i].x, &b[i].y);

	nr=0;
	for (i=1;i<=N;++i)
		 for (j=1;j<=N;++j){

			  p[++nr].d=dist(a[i].x,a[i].y,b[j].x,b[j].y);
			  p[nr].i=i;
			  p[nr].j=j;
		 }
	sort(p+1,p+nr+1,cmp);


	ls=1,ld=nr;
    while(ls<=ld)
    {
        int mij=(ls+ld)/2;
        if(bun(p[mij].d))
            ld=mij-1;
        else
			ls=mij+1;
    }

	printf("%.5lf ", p[ls].d);

	//if (N<=280){

	dest=2*N+1;
	for (i=1;i<=nr && p[i].d<=p[ls].d;++i){

		x=p[i].i;
		y=p[i].j+N;
	    C[x][y]=C[0][x]=C[y][dest]=1;
		g[x].push_back(make_pair(y,p[i].d));
		g[y].push_back(make_pair(x,-p[i].d));
		g[x].push_back(make_pair(0,0));
		g[0].push_back(make_pair(x,0));
		g[y].push_back(make_pair(dest,0));
		g[dest].push_back(make_pair(y,0));
	}

	double sol=0;
    while(dijkstra())
    {
        int Vmin=inf;
        for(i=dest;i!=0;i=tata[i])
            Vmin=min(Vmin,C[tata[i]][i]-F[tata[i]][i]);
        for(i=dest;i!=0;i=tata[i])
        {
            F[tata[i]][i]+=Vmin;
            F[i][tata[i]]-=Vmin;
        }
        if(Vmin)
           sol+=cost[dest];
	}
    printf("%.5lf\n",sol);
	//}


	return 0;
}