Cod sursa(job #64788)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 5 iunie 2007 17:38:56
Problema Adapost Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.61 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2*404
#define QMAX ((1<<18)-1)
#define eps 0.0001
#define INF 666000666

int N, Flow;
char F[NMAX][NMAX], C[NMAX][NMAX];
int t[NMAX], type[NMAX], cup[NMAX], inQ[NMAX], Q[QMAX];
double D[NMAX][NMAX], S[2][NMAX], A[2][NMAX], Dist[NMAX];
double Dmin, Dtot, Rmin;

void read()
{
        int i, j;

        freopen("adapost.in", "r", stdin);
        scanf("%d", &N);

        for (i = 1; i <= N; i++) scanf("%lf %lf", &S[0][i], &S[1][i]);
        for (i = 1; i <= N; i++) scanf("%lf %lf", &A[0][i], &A[1][i]);
}

void precompute()
{
        int i, j;

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++)
                D[i][N+j] = sqrt( (S[0][i]-A[0][j])*(S[0][i]-A[0][j]) + (S[1][i]-A[1][j])*(S[1][i]-A[1][j]) );

}

int bf(int sink)
{
        int i, j, lo, hi, dmin;

        for (i = 0; i < NMAX; i++)  {
            type[i] = t[i] = inQ[i] = 0;
            Dist[i] = INF; }

        Q[0] = sink; inQ[sink] = 1; t[sink] = cup[sink] = -1; Dist[sink] = 0;

        for (lo = 0, hi = 1; lo != hi; lo = (lo+1)&QMAX)
        {
                i = Q[lo];

                if (i<=N)
                {
                        for (j = N<<1; j >= N; j--)
                            if ( (cup[i] <= 0) && (F[i][j]<C[i][j]) && ((Dist[j]-Dist[i]-D[i][j])>eps) )
                            {
                                Dist[j] = Dist[i]+D[i][j];
                                t[j] = i; type[j] = 1;
                                if (!inQ[j]) inQ[j], Q[hi] = j, hi = (hi+1)&QMAX;
                            }
                }
                else
                    if ( (cup[i]) && (F[cup[i]-N][i]=='1') && ((Dist[cup[i]]-Dist[i]-D[cup[i]][i])> eps) )
                    {
                        Dist[cup[i]] = Dist[i]+D[cup[i]][i];
                        t[cup[i]] = i; type[cup[i]] = 2;
                        if (!inQ[cup[i]]) inQ[cup[i]] = 1, Q[hi] = cup[i], hi = (hi+1)&QMAX;
                    }
        }

        dmin = INF; j = sink;
        for (i = N<<1; i >= N; i--)
            if ((cup[i] == 0) && (Dist[i]-dmin)<eps) dmin = Dist[i], j = i;

        if (dmin<INF)
        {
                Dtot += dmin;
                for (i = j; i > 0; i = t[i])
                    if (type[i] == 1)
                    {
                        F[t[i]][i] = '1';
                        cup[i] = t[i];
                    }
                    else F[i][t[i]] = '0';
                return 1;
        }

        return 0;
}

void solve()
{
        int i, j;
        double lo = 0, hi = (1<<28), mij;

        while (lo<=hi)
        {
                mij = (lo+hi)/2.0;
                memset(F,'0',sizeof(F));
                memset(C,'0',sizeof(C));
                memset(cup,0,sizeof(cup));
                for (i = 1; i <= N; i++)
                    for (j = 1; j <= N; j++)
                        if (D[i][N+j] <= mij) C[i][N+j] = '1';
                Flow = Dtot = 0;
/*                for (i = 1; i <= N; i++)
                    for (j = N<<1; j >= N; j--)
                        if ( (cup[j]==0) && (C[i][j] == '1') )
                           { Flow++; cup[j] = i; F[i][j] = '1'; break; } */
                for (; Flow < N && bf(Flow+1); Flow++);
                if (Flow == N) hi = mij-eps, Rmin = mij, Dmin = Dtot;
                else lo = mij+eps;
        }
}

void write()
{
        freopen("adapost.out", "w", stdout);
        printf("%lf %lf\n", Dmin, Rmin);
}

int main()
{
        read();
        precompute();
        solve();
        write();
        return 0;
}