Cod sursa(job #478230)

Utilizator freak93Adrian Budau freak93 Data 17 august 2010 21:05:34
Problema Adapost Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.01 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<cassert>
#define x first
#define y second

using namespace std;

const char iname[]="adapost.in";
const char oname[]="adapost.out";
const int maxn=805;
const double inf=1e10;

ifstream f(iname);
ofstream g(oname);

pair<double,double> a[maxn],b[maxn];
double cost[maxn][maxn],dis[maxn],m[maxn*maxn],disd,aux,rez;
int n,i,j,k,p,A[maxn],been[maxn],S,D,C[maxn][maxn],F[maxn][maxn],step,flow,l[maxn],r[maxn],ok,heap[maxn],pos[maxn],done;
queue<int> Q;
vector<int> E[maxn];
double eps=1e-6;

inline double cmp(double a,double b)
{
    if(a+eps<b)
        return -1;
    if(b+eps<a)
        return 1;
    return 0;
}

double dist(pair<double,double> a,pair<double,double> b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int comb(int x)
{
    if(been[x])
        return 0;
    been[x]=1;
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(r[*it]==0)
        {
            l[x]=*it,r[*it]=x;
            return 1;
        }
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(comb(r[*it]))
        {
            l[x]=*it,r[*it]=x;
            return 1;
        }
    return 0;
}

void push(int x)
{
    int aux;
    while(dis[heap[x/2]]>dis[heap[x]])
    {
        aux=heap[x/2];
        heap[x/2]=heap[x];
        heap[x]=aux;
        pos[heap[x/2]]=x/2;
        pos[heap[x]]=x;
        x/=2;
    }
}

void pop(int x)
{
    int y=0,aux;
    while(y!=x)
    {
        y=x;
        if(y*2<=done&&cmp(dis[heap[y*2]],dis[heap[x]])==-1)
            x=y*2;
        if(y*2+1<=done&&cmp(dis[heap[y*2+1]],dis[heap[x]])==-1)
            x=y*2+1;
        aux=heap[x];heap[x]=heap[y];heap[y]=aux;
        pos[heap[x]]=x;
        pos[heap[y]]=y;
    }
}

void bellman()
{
    for(int i=1;i<=n;++i)
        dis[i]=inf;
    memset(been,0,sizeof(been));
    been[S]=1;
    dis[S]=0;
    Q.push(S);
    int x;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        been[x]=0;
        if(x==D)
            continue;
        for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
            if(F[x][*it]<C[x][*it]&&cmp(dis[x]+cost[x][*it],dis[*it])==-1)
            {
                dis[*it]=dis[x]+cost[x][*it];
                if(been[*it]==0)
                    been[*it]=1,Q.push(*it);
            }
    }
    disd=dis[D];
}

double dijkstra()
{
    for(int i=1;i<=n;++i)
        for(vector<int>::iterator it=E[i].begin();it!=E[i].end();++it)
            if(cmp(dis[i],inf)&&cmp(dis[*it],inf))
                cost[i][*it]+=dis[i]-dis[*it];

    for(int i=1;i<=n;++i)
        heap[i]=i,pos[i]=i,A[i]=-1,dis[i]=inf;
    heap[1]=S;heap[S]=1;
    pos[1]=S;pos[S]=1;
    done=n;
    dis[S]=0;
    A[S]=S;
    while(done>1&&dis[heap[1]]!=inf)
    {
        for(vector<int>::iterator it=E[heap[1]].begin();it!=E[heap[1]].end();++it)
            if(C[heap[1]][*it]>F[heap[1]][*it]&&cmp(dis[heap[1]]+cost[heap[1]][*it],dis[*it])==-1)
            {
                dis[*it]=dis[heap[1]]+cost[heap[1]][*it];
                A[*it]=heap[1];
                push(pos[*it]);
            }
        heap[1]=heap[done--];
        pos[heap[1]]=1;
        pop(1);
    }
    if(dis[D]!=inf)
    {
        for(int i=D;i!=S;i=A[i])
            F[A[i]][i]+=1,F[i][A[i]]-=1;
        disd+=dis[D];
        return 1*disd;
    }
    return inf;
}

int main()
{
    f>>n;
    D=2*n+1;
    S=2*n+2;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    for(i=1;i<=n;++i)
        f>>b[i].x>>b[i].y;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            cost[i][j+n]=-(cost[j+n][i]=-dist(a[i],b[j])),C[i][j+n]=1,m[++k]=cost[i][j+n];
    for(i=1;i<=n;++i)
        C[S][i]=1,C[i+n][D]=1,E[S].push_back(i);
    sort(m+1,m+k+1);
    for(step=1;step<k;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=k)
        {
            i+=step;
            for(j=1;j<=n;++j)
                vector<int>().swap(E[j]);
            for(j=1;j<=n;++j)
                for(p=n+1;p<=n*2;++p)
                    if(cost[j][p]<=m[i])
                        E[j].push_back(p);
            memset(l,0,sizeof(l));
            memset(r,0,sizeof(r));
            flow=0;
            do
            {
                ok=0;
                memset(been,0,sizeof(been));
                for(j=1;j<=n;++j)
                    if(l[j]==0)
                        ok+=comb(j);
                flow+=ok;
            }while(ok);
            if(flow==n)
                i-=step;
        }
    ++i;
    disd=0;
    for(j=1;j<=n;++j)
        vector<int>().swap(E[j]),vector<int>().swap(E[j+n]),E[j+n].push_back(D),E[D].push_back(j+n),E[j].push_back(S);
    for(j=1;j<=n;++j)
        for(p=n+1;p<=n*2;++p)
            if(cost[j][p]<=m[i])
                E[j].push_back(p),E[p].push_back(j);
    n*=2;
    ++n;++n;
    bellman();
    flow=0;
    memset(F,0,sizeof(F));
    while((aux=dijkstra())!=inf)
    {
        rez+=aux,++flow;
        if(flow==n)
            break;
    }
    assert(flow!=n);
    g.setf(ios::fixed,ios::floatfield);
    g.precision(5);
    g<<m[i]<<" "<<rez<<"\n";
}