Cod sursa(job #90627)

Utilizator sealTudose Vlad seal Data 9 octombrie 2007 21:00:37
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.34 kb
using namespace std;
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define Nm 401
#define eps 0.000001
#define Inf 2000000
#define sink (n<<1|1)
#define max(a,b) ((a)>(b)?(a):(b))
bool Viz[Nm<<1];
int Q[Nm*Nm<<2],G[Nm][Nm],Match[Nm<<1],Lev[Nm<<1],Pre[Nm<<1],Deg[Nm],n,lm;
double D[Nm][Nm],A[Nm*Nm],X[Nm<<1],Y[Nm<<1],Dm[Nm<<1],dmin,smin;

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()
{
    int l=0,r=-1,i,x,y;

    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=0;i<Deg[x];++i)
            {
                y=G[x][i];
                if(!Lev[y])
                {
                    Q[++r]=y;
                    Lev[y]=Lev[x]+1;
                }
            }
    }
}

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

    int i,y;

    for(i=0;i<Deg[x];++i)
    {
        y=G[x][i];
        if(Lev[y]==Lev[x]+1 && !Viz[y] && DFS(y))
        {
            Match[x]=y;
            Match[y]=x;
            return 1;
        }
    }
    return 0;
}

void construct_graph(double m)
{
    int i,j;

    memset(Deg,0,sizeof(Deg));
    for(i=1;i<=n;++i)
        for(j=n+1;j<=n<<1;++j)
            if(D[i][j-n]<=m+eps)
                G[i][Deg[i]++]=j;
}

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

    construct_graph(m);
    
    memset(Match,0,sizeof(Match));
    for(x=1;x<=n;++x)
        for(i=0;i<Deg[x];++i)
        {
            y=G[x][i];
            if(!Match[y])
            {
                Match[x]=y;
                Match[y]=x;
                ++ans;
                break;
            }
        }

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

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

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

    while(l<=r)
    {
        x=Q[l++];
        if(x>n)
        {
            if(Match[x])
            {
                if(Dm[x]-D[Match[x]][x-n]<Dm[Match[x]])
                {
                    Dm[Match[x]]=Dm[x]-D[Match[x]][x-n];
                    Pre[Match[x]]=x;
                    Q[++r]=Match[x];
                }
            }
            else
                if(Dm[x]<Dm[sink])
                {
                    Dm[sink]=Dm[x];
                    Pre[sink]=x;
                }
        }
        else
            for(i=0;i<Deg[x];++i)
            {
                y=G[x][i];
                if(y!=Match[x] && Dm[x]+D[x][y-n]<Dm[y])
                {
                    Dm[y]=Dm[x]+D[x][y-n];
                    Pre[y]=x;
                    Q[++r]=y;
                }
            }
    }
    return Dm[sink]!=Inf;
}

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

    l=r=0;
    for(i=1;i<=n;++i)
        for(j=n+1;j<=n<<1;++j)
            A[r++]=D[i][j-n]=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));

    sort(A,A+r); --r;
    while(l<r)
    {
        m=l+r>>1;
        if(Hopcroft_Karp(A[m])<n)
            l=m+1;
        else
            r=m;
    }
    
    dmin=A[l];
    construct_graph(dmin);
    memset(Match,0,sizeof(Match));
    while(Bellman_Ford())
    {
        smin+=Dm[sink];
        for(j=0,i=sink;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;
}