Cod sursa(job #469456)

Utilizator ionutz32Ilie Ionut ionutz32 Data 7 iulie 2010 18:59:22
Problema Adapost Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.94 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],tt[805],cuplaj,heap[805],mindif[805],x,first,aux,minim,st[405],dr[405];
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 pairup(int node)
{
    int i;
    if (viz[node])
        return 0;
    viz[node]=1;
    for (i=1;i<=n;++i)
        if (!dr[i] && cost[node][i+n]<=val[mid])
        {
            dr[i]=node;
            st[node]=i;
            return 1;
        }
    for (i=1;i<=n;++i)
        if (cost[node][i+n]<=val[mid])
            if (pairup(dr[i]))
            {
                dr[i]=node;
                st[node]=i;
                return 1;
            }
    return 0;
}

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(st,0,sizeof(st));
        memset(dr,0,sizeof(dr));
        do
        {
            k=true;
            memset(viz,0,sizeof(viz));
            for (i=1;i<=n;++i)
                if (!st[i] && pairup(i))
                    k=false;
        }
        while (!k);
        cuplaj=0;
        for (i=1;i<=n;++i)
            if (st[i])
                ++cuplaj;
        if (cuplaj==n)
            b=mid-1;
        else
            a=mid+1;
    }

    //flux maxim de cost minim

    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;
}