Cod sursa(job #89970)

Utilizator sealTudose Vlad seal Data 7 octombrie 2007 23:41:41
Problema Adapost Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include<stdio.h>
#include<string.h>
#include<math.h>
#define Nm 401
#define max(a,b) ((a)>(b)?(a):(b))
#define eps 0.001
#define Inf 2000000
double D[Nm][Nm<<1],X[Nm<<1],Y[Nm<<1],Dm[Nm<<1],dmin,smin;
int Q[Nm*Nm<<2],Match[Nm<<1],Lev[Nm<<1],Viz[Nm<<1],Pre[Nm<<1],n,lm;

void read()
{
    int i;

    freopen("adapost.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n<<1;++i)
        scanf("%lf%lf",X+i,Y+i);
}

void BFS(double m)
{
    int l=0,r=-1,x,i;

    memset(Lev,0,sizeof(Lev));
    for(i=1;i<=n;++i)
        if(!Match[i])
        {
            Lev[i]=1;
            Q[++r]=i;
        }

    lm=0;
    while(l<=r)
    {
        x=Q[l++];
        if(x>n)
        {
            if(Match[x])
            {
                Q[++r]=Match[x];
                Lev[Match[x]]=Lev[x]+1;
            }
            else
                if(!lm)
                    lm=Lev[x];
        }
        else
            for(i=n+1;i<=n<<1;++i)
                if(D[x][i]<=m && !Lev[i])
                {
                    Q[++r]=i;
                    Lev[i]=Lev[x]+1;
                }
    }
}

int DFS(int x, double m)
{
    Viz[x]=1;
    if(Lev[x]==lm)
        return Match[x]==0;
    if(x>n)
        return DFS(Match[x],m);

    int i;

    for(i=n+1;i<=n<<1;++i)
        if(D[x][i]<=m && Lev[i]==Lev[x]+1 && !Viz[i] && DFS(i,m))
        {
            Match[x]=i;
            Match[i]=x;
            return 1;
        }
    return 0;
}

int Hopcroft_Karp(double m)
{
    int i,j,ans=0;

    memset(Match,0,sizeof(Match));
    for(i=1;i<=n;++i)
        for(j=n+1;j<=n<<1;++j)
            if(D[i][j]<=m && !Match[j])
            {
                Match[i]=j;
                Match[j]=i;
                ++ans;
                break;
            }

    while(1)
    {
        BFS(m);
        if(!lm)
            break;
        memset(Viz,0,sizeof(Viz));
        for(i=1;i<=n;++i)
            if(!Match[i] && DFS(i,m))
                ++ans;
    }
    return ans;
}

int Bellman_Ford()
{
    int l=0,r=-1,x,i;

    for(i=1;i<=(n<<1|1);++i)
        Dm[i]=Inf;
    for(i=1;i<=n;++i)
        if(!Match[i])
        {
            Q[++r]=i;
            Dm[i]=Pre[i]=0;
        }

    while(l<=r)
    {
        x=Q[l++];
        if(x>n)
        {
            if(Match[x])
            {
                if(Dm[x]-D[Match[x]][x]<Dm[Match[x]])
                {
                    Dm[Match[x]]=Dm[x]-D[Match[x]][x];
                    Pre[Match[x]]=x;
                    Q[++r]=Match[x];
                }
            }
            else
                if(Dm[x]<Dm[n<<1|1])
                {
                    Dm[n<<1|1]=Dm[x];
                    Pre[n<<1|1]=x;
                }
        }
        else
            for(i=n+1;i<=n<<1;++i)
                if(D[x][i]<=dmin && i!=Match[x] && Dm[x]+D[x][i]<Dm[i])
                {
                    Dm[i]=Dm[x]+D[x][i];
                    Pre[i]=x;
                    Q[++r]=i;
                }
    }
    return Dm[n<<1|1]!=Inf;
}

void solve()
{
    int i,j;
    double l=0,r=0,m;

    for(i=1;i<=n;++i)
        for(j=n+1;j<=n<<1;++j)
        {
            D[i][j]=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
            r=max(r,D[i][j]);
        }

    while(r-l>eps)
    {
        m=(l+r)/2;
        if(Hopcroft_Karp(m)<n)
            l=m+eps;
        else
            r=m;
    }
    
    dmin=l;
    memset(Match,0,sizeof(Match));
    while(Bellman_Ford())
    {
        smin+=Dm[n<<1|1];
        for(j=0,i=n<<1|1;i;i=Pre[i],j^=1)
            if(j)
            {
                Match[i]=Pre[i];
                Match[Pre[i]]=i;
            }
    }
}

void write()
{
    freopen("adapost.out","w",stdout);
    printf("%lf %lf\n",dmin,smin);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}