Cod sursa(job #469508)

Utilizator ionutz32Ilie Ionut ionutz32 Data 7 iulie 2010 23:41:47
Problema Adapost Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.17 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#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];
struct cmp
{
    bool operator()(const double &a, const double &b)const
    {
        return a<b;
    }
};
int n,i,j,f[805][805],cap[805][805],a,b,mid,viz[805],tt[805],cuplaj,mindif[805],first,aux,minim,st[405],dr[405];
double val[160005],cost[805][805],sol,dist[805];
bool k;
class heap_cmp
{
    public:
        inline bool operator()(const int &x,const int &y)
        {
            return dist[x]>dist[y];
        }
};
priority_queue<int,vector<int>,heap_cmp> heap;

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 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;
        }
        viz[sursa]=1;
        heap.push(sursa);
        mindif[sursa]=inf;
        dist[sursa]=0;
        while (!heap.empty())
        {
            first=heap.top();
            heap.pop();
            viz[first]=0;
            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.push(*u);
                        viz[*u]=1;
                    }
                }
        }
        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;
}