Cod sursa(job #485774)

Utilizator freak93Adrian Budau freak93 Data 19 septembrie 2010 14:49:18
Problema Adapost Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#define punct pair<double,double>
#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=1e25;
ifstream f(iname);
ofstream g(oname);

vector<int> E[maxn];
int r[maxn],l[maxn],S,D,A[maxn],been[maxn],C[maxn][maxn],F[maxn][maxn],n,i,j,p,k,step,ok;
double dis[maxn],cost[maxn][maxn],rez,m[maxn*maxn];
queue<int> Q;
punct a[maxn],b[maxn];

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

int match(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]==-1)
        {
            l[x]=*it;
            r[*it]=x;
            return 1;
        }
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(match(r[*it])==1)
        {
            l[x]=*it;
            r[*it]=x;
            return 1;
        }
    return 0;
}

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

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