Cod sursa(job #841448)

Utilizator stoicatheoFlirk Navok stoicatheo Data 24 decembrie 2012 11:26:27
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.25 kb
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <math.h>
#define NMAX 405
#define LMAX 811
#define prec 0.001
#define INF 100000000
#define pb push_back
using namespace std;
struct punct{double x,y;};
punct A[NMAX],B[NMAX];
int n,st[NMAX],dr[NMAX],sursa,dest,E[LMAX][LMAX],F[LMAX][LMAX],dad[LMAX];
double C[NMAX][NMAX],rez1,rez2,dist[LMAX];
vector <int> D[LMAX];
vector <double> G[LMAX];
queue <int> Q;
char marc[NMAX],in[LMAX],still;
double d_pcte(punct a,punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void read()
{
    scanf("%d",&n);
    int i,j;
    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);
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            C[i][j]=d_pcte(A[i],B[j]);
}
void sterge()
{
    int i;
    for (i=1; i<=n; i++)
        D[i].clear();
    memset(st,0,sizeof(st));
    memset(dr,0,sizeof(dr));
}
void construct(double val)
{
    sterge();
    int i,j;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (C[i][j]<val)
                D[i].pb(j);
}
int pairup(int nod)
{
    marc[nod]=1;
    int i,vec;
    for (i=0; i<D[nod].size(); i++)
    {
        vec=D[nod][i];
        if (!dr[vec])
        {
            st[nod]=vec; dr[vec]=nod;
            return 1;
        }
    }
    for (i=0; i<D[nod].size(); i++)
    {
        vec=D[nod][i];
        if (!marc[dr[vec]] && pairup(dr[vec]))
        {
            st[nod]=vec; dr[vec]=nod;
            return 1;
        }
    }
    return 0;
}
inline int ok(double val)
{
    construct(val);
    int i,fin=1,act=0;
    while (fin)
    {
        fin=0;
        memset(marc,0,sizeof(marc));
        for (i=1; i<=n; i++)
            if (!st[i])
                if (pairup(i))
                {
                    act++;
                    fin=1;
                }
    }
    return act==n;
}
double cbin()
{
    double st=0,dr=20000,mij;
    while (dr-st>prec)
    {
        mij=(st+dr)/2;
        if (ok(mij))
            dr=mij;
        else
            st=mij;
    }
    return st;
}
inline int min(int x,int y)
{
    return x<y ? x : y;
}
void bford()
{
    int i,j,nod,vec,val;
    for (i=1; i<=dest; i++)
        dist[i]=INF;
    Q.push(sursa); in[sursa]=1;
    while (!Q.empty())
    {
        nod=Q.front();
        Q.pop();
        in[nod]=0;
        for (i=0; i<D[nod].size(); i++)
        {
            vec=D[nod][i];
            if (E[nod][vec]-F[nod][vec]>0 && dist[vec]>dist[nod]+G[nod][i])
            {
                dad[vec]=nod;
                dist[vec]=dist[nod]+G[nod][i];
                if (!in[vec] && vec!=dest)
                    Q.push(vec),in[vec]=1;
            }
        }
    }
    if (dist[dest]!=INF)
    {
        still=1;
        for (j=0; j<D[dest].size(); j++)
        {
            nod=D[dest][j];
            if (dist[nod]==INF || F[nod][dest]==E[nod][dest])
                continue ;
            dad[dest]=nod;
            val=INF;
            for (i=dest; i!=sursa; i=dad[i])
                val=min(val,E[dad[i]][i]-F[dad[i]][i]);
            for (i=dest; i!=sursa; i=dad[i])
            {
                F[dad[i]][i]+=val;
                F[i][dad[i]]-=val;
            }
            rez2+=val*dist[nod];
        }
    }
}
void fa_graf()
{
    int i,j;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (C[i][j]<rez1+prec)
            {
                E[i][j+n]=1;
                D[i].pb(j+n); G[i].pb(C[i][j]);
                D[j+n].pb(i); G[j+n].pb(-C[i][j]);
            }
    sursa=0; dest=2*n+1;
    for (i=1; i<=n; i++)
    {
        E[sursa][i]=1;
        D[sursa].pb(i);  G[sursa].pb(0); D[i].pb(sursa); G[i].pb(0);
        E[i+n][dest]=1;
        D[i+n].pb(dest); G[i+n].pb(0); D[dest].pb(i+n);  G[dest].pb(0);
    }
}
void solve()
{
    sterge();
    fa_graf();
    still=1;
    while (still)
    {
        still=0;
        bford();
    }
}
int main()
{
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
    read();
    rez1=cbin();
    printf("%lf ",rez1);
    solve();
    printf("%lf\n",rez2);
    return 0;
}