Cod sursa(job #2798611)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:53:29
Problema Adapost Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.96 kb
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>

#define maxn 405
#define pb push_back
#define mp make_pair
#define INF (1<<29)
#define eps (1e-4)

using namespace std;

FILE*f=fopen("adapost.in","r");
FILE*g=fopen("adapost.out","w");

int n;
int L[maxn],R[maxn],viz[maxn];
double v[maxn*maxn],lim,Dist[maxn<<1],prep[maxn][maxn];
int S,D;
int Cp[maxn<<1][maxn<<1],F[maxn<<1][maxn<<1],inQ[maxn<<1],T[maxn<<1];
vector< pair<int,double> >G[maxn];
vector<int>V[maxn<<1]; queue<int>Q;
double cost[maxn<<1][maxn<<1];

struct pct{
    double x,y;
}A[maxn],B[maxn];

inline void citire () {

    fscanf(f,"%d",&n);
    for ( int i = 1 ; i <= n ; ++i ){
        fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
    }
    for ( int i = 1 ; i <= n ; ++i ){
        fscanf(f,"%lf %lf",&B[i].x,&B[i].y);
    }
}

inline double dist ( const pct &a , const pct &b ){
    double d = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return sqrt(d);
}

bool pairup ( int nod ){
    if ( viz[nod] ) return 0;
    viz[nod] = 1;

    for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
        int nodvcn = itt->first; double cost = itt->second;
        if ( cost <= lim ){
            if ( !R[nodvcn] ){
                L[nod] = nodvcn; R[nodvcn] = nod;
                return 1;
            }
        }
    }

    for ( vector< pair<int,double> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
        int nodvcn = itt->first; double cost = itt->second;
        if ( cost <= lim ){
            if ( pairup(R[nodvcn]) ){
                L[nod] = nodvcn; R[nodvcn] = nod;
                return 1;
            }
        }
    }

    return 0;
}

inline bool cuplaj () {

    for ( int i = 1 ; i <= n ; ++i ) L[i] = R[i] = 0;
    int ok = 1;
    do{
        ok = 0; for ( int i = 1 ; i <= n ; ++i ) viz[i] = 0;
        for ( int i = 1 ; i <= n ; ++i ){
            if ( !L[i] )
                ok |= pairup(i);
        }
    }while(ok);

    int cuplaj = 0;
    for ( int i = 1 ; i <= n ; ++i ){
        if ( L[i] ){
            ++cuplaj;
        }
    }

    return cuplaj == n;
}

inline void build () {

    for ( int i = 1 ; i <= n ; ++i ){
        G[i].clear();
    }

    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= n ; ++j ){
            if ( prep[i][j] <= lim ){
                G[i].pb(mp(j,prep[i][j]));
            }
        }
    }
}

inline void first () {

    int index = 0;
    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= n ; ++j ){
            v[++index] = dist(A[i],B[j]);
            prep[i][j] = v[index];
        }
    }
    sort(v+1,v+index+1);

    int p = 1,m,u = index;
    while ( p <= u ){
        m = (p + u) >> 1;
        lim = v[m];

        build();
        if ( cuplaj() ){
            u = m - 1;
        }
        else{
            p = m + 1;
        }
    }

    lim = v[p];
    fprintf(g,"%.5lf ",lim);
}

inline bool bellman_ford () {

    Q.push(S); inQ[S] = 1;

    for ( int i = 1 ; i <= D ; ++i ){
        Dist[i] = INF;
    }
    Dist[S] = 0;

    while ( !Q.empty() ){
        int nod = Q.front(); Q.pop(); inQ[nod] = 0;

        for ( vector<int>::iterator itt = V[nod].begin() ; itt != V[nod].end() ; ++itt ){
            int nodvcn = (*itt);
            if ( Dist[nodvcn] > Dist[nod] + cost[nod][nodvcn] && F[nod][nodvcn] < Cp[nod][nodvcn] ){
                Dist[nodvcn] = Dist[nod] + cost[nod][nodvcn]; T[nodvcn] = nod;
                if ( !inQ[nodvcn] ){
                    Q.push(nodvcn);
                    inQ[nodvcn] = 1;
                }
            }
        }
    }

    return Dist[D] != INF;
}

inline void flux () {
    double flow_cost = 0;

    while ( bellman_ford() ){

        int nod;
        for ( nod = D ; T[nod] ; nod = T[nod] ){
            ++F[T[nod]][nod];
            --F[nod][T[nod]];
        }

        flow_cost += Dist[D];
    }

    fprintf(g,"%.5lf\n",flow_cost);
}

inline bool equal ( const double &a , const double &b ){
    double dif = a-b;
    if ( dif < 0 )   dif = -dif;
    return dif < eps;
}

inline void second () {
    S = n+n+1; D = n+n+2;

    for ( int i = 1 ; i <= n ; ++i ){
        V[S].pb(i); V[i].pb(S);
        Cp[S][i] = 1;
    }

    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= n ; ++j ){
            int nod = j + n;
            cost[i][nod] = prep[i][j];

            if ( cost[i][nod] <= lim || equal(cost[i][nod],lim) ){
                V[i].pb(nod); V[nod].pb(i);
                Cp[i][nod] = 1;
                cost[nod][i] = -cost[i][nod];
            }
        }
    }

    for ( int i = 1 ; i <= n ; ++i ){
        int nod = i + n;
        V[nod].pb(D);
        Cp[nod][D] = 1;
    }

    flux();
}

int main () {

    citire();
    first();
    second();

    fclose(f);
    fclose(g);

    return 0;
}