Cod sursa(job #460748)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 3 iunie 2010 20:02:45
Problema Adapost Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.66 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define NMAX 401
#define INF 999999999
#define src 2*N+1

typedef struct
{
	int x,y;
     double cost;
}t_e;

void read();
void solve();
int cupleaza(int nod);
int lee();
void flux();
double d(double a,double b,double x,double y);
int cmp(const void *a,const void *b);

int N,nrv[2*NMAX],V[2*NMAX][NMAX],cupl[2*NMAX],lim,seen[2*NMAX],prev[2*NMAX],cap[2*NMAX][2*NMAX],cd[NMAX*NMAX],seen[2*NMAX];
double X[2*NMAX],Y[2*NMAX],sum;
double dd[2*NMAX];
double dist[NMAX][NMAX];
t_e edge[NMAX*NMAX];

int main(void)
{
	freopen("adapost.in","r",stdin);
     freopen("adapost.out","w",stdout);

     read();
     solve();
	return 0;
}

void read()
{
	int i,j;
     
	scanf("%d ",&N);
     for(i=0;i<2*N;i++)
     	scanf("%lf %lf ",&X[i],&Y[i]);
          
     for(i=0;i<N;i++)
     for(j=N;j<2*N;j++)
     {
     edge[lim].cost=d(X[i],Y[i],X[j],Y[j]);
     dist[i][j-N]=edge[lim].cost;
     edge[lim].x=i,edge[lim].y=j;
     lim++;
     }
     qsort(edge,lim,sizeof(t_e),cmp);
}

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

int cmp(const void *a,const void *b)
{
	if((*(t_e *)a).cost<(*(t_e *)b).cost)
     	return -1;
     	return 1;
}

void solve()
{
	int i,z,flag,match=0;

     memset(cupl,-1,sizeof(cupl));
     for(z=0;z<lim;z++)
     {
     
     	flag=1;
          V[edge[z].x][nrv[edge[z].x]++]=edge[z].y;
          V[edge[z].y][nrv[edge[z].y]++]=edge[z].x;
          cap[edge[z].x][edge[z].y]=1;
          cap[src][edge[z].x]=1,cap[edge[z].y][2*N]=1,prev[edge[z].x]=src;
 		while(flag)
          {
          	flag=0;
               for(i=0;i<N;i++)
               if(cupl[i]==-1&&cupleaza(i))
               	flag=1,match++;
               memset(seen,0,sizeof(seen));
          }
          if(match>=N)
          break;
     }
     flux();
     printf("%lf %lf\n",edge[z].cost,sum);
}

int cupleaza(int nod)
{
	int i;

     seen[nod]=1;
     if(cupl[nod]!=-1) seen[cupl[nod]]=1;
     for(i=0;i<nrv[nod];i++)
	if(!seen[V[nod][i]]&&(cupl[V[nod][i]]==-1||cupleaza(cupl[V[nod][i]])))
     {
     	cupl[nod]=(V[nod][i]),cupl[V[nod][i]]=nod;
          return 1;
     }
     return 0;
}

void flux()
{
	int x;

     do
     {
     	if(lee())
          {
          	for(x=2*N;x!=src;x=prev[x])
               {
               	cap[prev[x]][x]--,cap[x][prev[x]]++;
                    if(prev[x]<N)
                    	sum+=dist[prev[x]][x-N];
                    else if(prev[x]<2*N)
                    	sum-=dist[x][prev[x]-N];
               }
          }else break;
     }while(1);
}

int lee()
{
	int i,j,z,b,e,x;

     e=-1;
     for(i=0;i<=2*N;i++)
     dd[i]=INF,seen[i]=0;
     for(i=0;i<N;i++)
     if(0<cap[src][i]) dd[i]=0,prev[i]=src,cd[++e]=i,seen[i]=1;
	for(b=0;b<=e;b++)
     {
     x=cd[b];
     if(0<cap[x][2*N]&&dd[2*N]>dd[x])
     {
     	dd[2*N]=dd[x];
          prev[2*N]=x;
     }
     if(x<N)
     for(z=0;z<nrv[x];z++)
     {
     	j=V[x][z];
          if(0<cap[x][j]&&dd[x]!=INF&&dd[j]>dd[x]+dist[x][j-N])
          {
          	dd[j]=dd[x]+dist[x][j-N],prev[j]=x;
               if(!seen[j]&&dd[j]<dd[2*N])
               cd[++e]=j,seen[j]=1;
          }
     }
     else
     for(z=0;z<nrv[x];z++)
     {
     	j=V[x][z];
          if(0<cap[x][j]&&dd[x]!=INF&&dd[j]>dd[x]-dist[j][x-N])
          {
          	dd[j]=dd[x]-dist[j][x-N],prev[j]=x;
               if(!seen[j]&&dd[j]<dd[2*N])
               cd[++e]=j,seen[j]=1;
          }
     }
     seen[x]=0;
     }
     if(dd[2*N]<INF)
     	return 1;
     return 0;
}