Cod sursa(job #1598169)

Utilizator AndreiGrigorasAndrei Grigoras AndreiGrigoras Data 12 februarie 2016 17:41:57
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.6 kb
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>

#define N 810
#define INF 1000000.0

using namespace std;

ifstream f("adapost.in");
ofstream g("adapost.out");

int n,i,j,x,ok,flux,nr,li,dest,ls,mij,sol,t[N],viz[N],cap[N][N],fl[N][N],st[N],dr[N];

double cost,di[N][N],a[N*N],d[N];

struct punct{double x,y;}p[N],ad[N];

queue<int>q;

vector<pair<int,double> >v[N];
vector<int>gr[N];

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

inline bool cupleaza(int x){
    if(viz[x])
        return 0;

    viz[x] = 1;

    for(vector<int>::iterator it = gr[x].begin() ; it != gr[x].end() ; ++ it)
        if(!st[*it] || cupleaza(st[*it]))
        {
            st[*it] = x;
            dr[x] = *it;

            return 1;
        }

    return 0;
}

inline int cm(){
    ok = 1;
    int nr = 0;
    memset(dr,0,sizeof(dr));
    memset(st,0,sizeof(st));

    while(ok)
    {
        memset(viz,0,sizeof(viz));
        ok = 0;

        for(int i = 1 ; i <= n ; ++ i)
            if(!dr[i] && cupleaza(i))
            ok = 1 , ++ nr;
    }

    return nr;
}

inline bool bf(){
    for(int i = 1 ; i <= dest ; ++ i)
        d[i] = INF;

    q.push(0);
    viz[0] = 1;
    d[0] = 0;

    while(!q.empty())
    {
        x = q.front();
        q.pop();
        viz[x] = 0;

        if(x == dest)
            continue;

        for(vector<pair<int,double> >::iterator it = v[x].begin() ; it != v[x].end() ; ++ it)
            if(d[it->first] > d[x] + it->second && cap[x][it->first])
            {
                d[it->first] = d[x] + it->second;
                t[it->first] = x;

                if(!viz[it->first])
                {
                    viz[it->first] = 1;
                    q.push(it->first);
                }
            }
    }

    return d[dest] != INF;
}

inline void fmcm(){

    cost = 0;
    memset(viz,0,sizeof(viz));

    while(bf())
    {
        x = dest;

        while(x)
        {
            -- cap[t[x]][x];
            ++ cap[x][t[x]];

            x = t[x];

        }
        cost += d[dest];
    }

}

inline void fa_graf(double x){

    for(i = 1 ; i <= n ; ++ i)
    {
        v[0].push_back(make_pair(i , 0));
        cap[0][i] = 1;

        v[i + n].push_back(make_pair(dest , 0));
        cap[i + n][dest] = 1;

        for(j = 1 ; j <= n ; ++ j)
            if(di[i][j] <= x)
            {
                v[i].push_back(make_pair(n + j , di[i][j]));
                v[n + j].push_back(make_pair(i , -di[i][j]));

                cap[i][n + j] = 1;
            }
    }
}

inline bool verif(double x){
    for(i = 1 ; i <= n ; ++ i)
        gr[i].clear();

    for(i = 1 ; i <= n ; ++ i)
    {
        for(j = 1 ; j <= n ; ++ j)
            if(di[i][j] <= x)
            {
                gr[i].push_back(j);
            }
    }

    if(cm() == n)
        return 1;

    return 0;
}

int main()
{
    f >> n;

    dest = n * 2 + 1;

    for(i = 1 ; i <= n ; ++ i)
    {
        f >> p[i].x >> p[i].y ;
    }

    for(i = 1 ; i <= n ; ++ i)
    {
        f >> ad[i].x >> ad[i].y ;
    }

    for(i = 1 ; i <= n ; ++ i)
        for(j = 1 ; j <= n ; ++ j)
        di[i][j] = dist(p[i] , ad[j]),
        a[++ nr] = di[i][j];

    sort(a + 1 , a + nr + 1);

    li = 1;
    ls = nr;

    while(li <= ls)
    {
        mij = (li + ls)>>1;

        if(verif(a[mij]))
        {
            sol = mij;
            ls = mij - 1;
        }
        else
            li = mij + 1;
    }
    fa_graf(a[sol]);
    fmcm();

    g << fixed << setprecision(10) << a[sol] << ' ' << cost << '\n';

    return 0;
}