Cod sursa(job #469433)

Utilizator ionutz32Ilie Ionut ionutz32 Data 7 iulie 2010 18:38:50
Problema Adapost Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.61 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <cstring>
#define sursa (2*n+1)
#define dest (2*n+2)
#define inf 0x7fffffff

using namespace std;

vector<int> graf[805];
vector<int>::iterator u;
struct per
{
    double x,y;
} v[405],ad[405];
int n,i,j,f[805][805],cap[805][805],a,b,mid,viz[805],st,dr,q[805],tt[805],difmin,flow,heap[805],mindif[805],x,first,aux,minim;
double val[160005],cost[805][805],sol,dist[805];
bool k;

inline double plandist(per punct1,per punct2)
{
    return sqrt((punct1.x-punct2.x)*(punct1.x-punct2.x)+(punct1.y-punct2.y)*(punct1.y-punct2.y));
}

int cmp(const double &a,const double &b)
{
    return a<b;
}

inline void heap_up(int p)
{
    while (p>1 && dist[heap[p]]<dist[heap[p>>1]])
    {
        aux=heap[p];
        heap[p]=heap[p>>1];
        heap[p>>1]=aux;
        viz[heap[p]]=p;
        viz[heap[p>>1]]=p>>1;
        p>>=1;
    }
}

inline void heap_down(int p)
{
    while ((p*2<=x && dist[heap[p]]>dist[heap[p*2]]) || (p*2+1<=x && dist[heap[p]]>dist[heap[p*2+1]]))
    {
        if (p*2+1<=x)
            if (dist[heap[p*2]]<dist[heap[p*2+1]])
                minim=p*2;
            else
                minim=p*2+1;
        else
            minim=p*2;
        aux=heap[p];
        heap[p]=heap[minim];
        heap[minim]=aux;
        viz[heap[p]]=p;
        viz[heap[minim]]=minim;
        p=minim;
    }
}

int main()
{
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
        scanf("%lf %lf",&v[i].x,&v[i].y);
    for (i=1;i<=n;++i)
    {
        scanf("%lf %lf",&ad[i].x,&ad[i].y);
        for (j=1;j<=n;++j)
        {
            val[(i-1)*n+j]=plandist(ad[i],v[j]);
            graf[j].push_back(i+n);
            graf[i+n].push_back(j);
            cost[j][i+n]=val[(i-1)*n+j];
            cap[j][i+n]=1;
            cost[i+n][j]=-cost[j][i+n];
        }
        graf[sursa].push_back(i);
        graf[i].push_back(sursa);
        cap[sursa][i]=1;
        graf[i+n].push_back(dest);
        graf[dest].push_back(i+n);
        cap[i+n][dest]=1;
    }
    sort(val+1,val+n*n+1,cmp);
    a=1;
    b=n*n;
    while (a<=b)
    {
        mid=a+((b-a)>>1);
        memset(f,0,sizeof(f));
        flow=0;
        k=true;
        while (k)
        {
            k=false;
            memset(viz,0,sizeof(viz));
            q[1]=sursa;
            viz[sursa]=1;
            for (st=dr=1;st<=dr;++st)
                if (q[st]==dest)
                    k=true;
                else
                    for (u=graf[q[st]].begin();u!=graf[q[st]].end();++u)
                        if (!viz[*u] && cap[q[st]][*u]>f[q[st]][*u] && cost[q[st]][*u]<=val[mid] && cost[*u][q[st]]<=val[mid])
                        {
                            q[++dr]=*u;
                            viz[*u]=1;
                            tt[*u]=q[st];;
                        }
            if (k)
                for (u=graf[dest].begin();u!=graf[dest].end();++u)
                    if (viz[*u] && cap[*u][dest]>f[*u][dest])
                    {
                        difmin=cap[*u][dest]-f[*u][dest];
                        for (i=*u;i!=sursa;i=tt[i])
                            if (cap[tt[i]][i]-f[tt[i]][i]<difmin)
                                difmin=cap[tt[i]][i]-f[tt[i]][i];
                        if (difmin>0)
                        {
                            tt[dest]=*u;
                            for (i=dest;i!=sursa;i=tt[i])
                            {
                                f[tt[i]][i]+=difmin;
                                f[i][tt[i]]-=difmin;
                            }
                            flow+=difmin;
                        }
                    }
        }
        if (flow==n)
            b=mid-1;
        else
            a=mid+1;
    }
    memset(f,0,sizeof(f));
    k=true;
    while (k)
    {
        k=false;
        for (i=1;i<=dest;++i)
        {
            viz[i]=0;
            dist[i]=inf;
        }
        heap[1]=sursa;
        viz[sursa]=1;
        heap[1]=sursa;
        mindif[sursa]=inf;
        dist[sursa]=0;
        x=1;
        while (x)
        {
            first=heap[1];
            viz[first]=0;
            if (x==1)
                x=0;
            else
            {
                heap[1]=heap[x--];
                viz[heap[1]]=1;
                heap_down(1);
            }
            if (first==dest)
                k=true;
            for (u=graf[first].begin();u!=graf[first].end();++u)
                if (cap[first][*u]>f[first][*u] && dist[first]+cost[first][*u]<dist[*u] && cost[first][*u]<=val[b+1] && cost[*u][first]<=val[b+1])
                {
                    dist[*u]=dist[first]+cost[first][*u];
                    if (cap[first][*u]-f[first][*u]<mindif[first])
                        mindif[*u]=cap[first][*u]-f[first][*u];
                    else
                        mindif[*u]=mindif[first];
                    tt[*u]=first;
                    if (viz[*u])
                        heap_up(viz[*u]);
                    else
                    {
                        heap[++x]=*u;
                        viz[*u]=x;
                        heap_up(x);
                    }
                }
        }
        if (k)
            for (i=dest;i!=sursa;i=tt[i])
            {
                sol+=cost[tt[i]][i]*mindif[dest];
                f[tt[i]][i]+=mindif[dest];
                f[i][tt[i]]-=mindif[dest];
            }
    }
    printf("%.5lf %.5lf",val[b+1],sol);
    return 0;
}