Cod sursa(job #953083)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:58:33
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.14 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;
}