Cod sursa(job #402361)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 23 februarie 2010 20:18:19
Problema Adapost Scor 9
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.88 kb
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#define Nmx 505
#define INF 1000001
#define Mmx 1002
#define pb push_back
#define mp make_pair

using namespace std;

struct coord{ double x,y;};
int n,nr,viz[Mmx],dest;
int r[Nmx],l[Nmx];
int prec[Mmx],F[Mmx][Mmx],C[Mmx][Mmx],Q[Mmx*100];
double cost[Mmx];
coord a[Nmx],b[Nmx];
vector<int> g[Nmx*2];
vector< pair< int,double > > G[Mmx];

struct date{
    int x1,x2;
    double d;
}c[Nmx*3];

double dist(double x,double y,double x1,double y1)
{
    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}

bool cmp(const date &a,const date &b)
{
    return a.d<b.d;
}

void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&b[i].x,&b[i].y);
    int x,y;
    dest=n+n+1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            c[++nr].d=dist(a[i].x,a[i].y,b[j].x,b[j].y);
            c[nr].x1=i;c[nr].x2=j;
            x=i;y=j+n;
            C[x][y]=C[0][x]=C[y][dest]=1;
            G[x].pb(mp(0,0));
            G[0].pb(mp(x,0));
            G[x].pb(mp(y,c[nr].d));
            G[y].pb(mp(x,-c[nr].d));
            G[y].pb(mp(dest,0));
            G[dest].pb(mp(y,0));
        }
    sort(c+1,c+nr+1,cmp);
}

int pairup (int nod)
{
    int i;
    if (viz[nod])
        return 0;
    viz[nod]=1;
    for (i=0; i<(int)g[nod].size (); ++i)
        if (!r[g[nod][i]])
        {
            r[g[nod][i]]=nod;
            l[nod]=g[nod][i];
            return 1;
        }
    for (i=0; i<(int)g[nod].size (); ++i)
        if (pairup (r[g[nod][i]]))
        {
            l[nod]=g[nod][i];
            r[g[nod][i]]=nod;
            return 1;
        }
    return 0;
}

void build_graph(double x)
{
    for(int i=1;i<=n;++i)
    {
        g[i].clear();
        l[i]=0;
        r[i]=0;
    }
    for(int i=1;i<=nr&&c[i].d<=x;++i)
        g[c[i].x1].push_back(c[i].x2);

}


int este(double x)
{
    build_graph(x);
    int i,ok,cupl=0;
    do
    {
        ok=0;
        memset(viz,0,sizeof (viz));
        for (i=1; i<=n; ++i)
            if (!l[i] && pairup (i))
            {
                ++cupl;
                ok=1;
            }
    }
    while (ok);
    if(cupl!=n)
        return 0;
    return 1;
}

void solve()
{
    int st=1,dr=nr;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(este(c[mij].d))
            dr=mij-1;
        else st=mij+1;
    }
    printf("%lf ",c[st].d);
}


int belmand()
{
    vector<pair <int,double> >:: iterator it;
    int st,dr,nod;
    for(int i=1;i<=dest;++i)
        cost[i]=INF;
    Q[st=dr=1]=0;
    for(cost[0]=0;st<=dr;)
    {
        nod=Q[st];
        for(it=G[nod].begin();it!=G[nod].end();++it)
            if(C[nod][it->first]-F[nod][it->first]>0&&cost[nod]+it->second<cost[it->first])
            {
                cost[it->first]=cost[nod]+it->second;
                prec[it->first]=nod;
                if(!viz[it->first])
                {
                    viz[it->first]=1;
                    Q[++dr]=it->first;
                }
            }
        viz[Q[st+1]]=0;
        ++st;
    }
    if (cost[dest] < INF) {
        int flux = INF;
        for (int i = dest; i != 0; i = prec[i])
            flux = min(flux, C[prec[i]][i] - F[prec[i]][i]);
        for (int i = dest; i != 0; i = prec[i]) {
            F[prec[i]][i] += flux;
            F[i][prec[i]] -= flux;
        }
        return flux * cost[dest];
    }
    return 0;
}

void flux()
{
    int cupl=0;
    double sol=0;
    while(belmand())
    {
        ++cupl;
        sol+=cost[dest];
    }
    printf("%lf\n",sol);
}

int main()
{
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
    citire();
    solve();
    flux();
    return 0;
}