Cod sursa(job #64793)

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

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

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]);

        T = 2*N+1;
}

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 i, j, lo, hi;

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

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

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

        return 0;
}

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

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

                Dtot = 0;
                for (i = N; i < T; i++) Dtot += D[cup[i]][i];
                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", Rmin, Dmin);
}

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