Cod sursa(job #5588)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 13 ianuarie 2007 13:10:01
Problema Adapost Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <stdio.h>
#include <string.h>
#include <math.h>

#define NMAX 402
#define CMAX (1<<11)
#define INF 666666

int F[NMAX][2*NMAX], InQ[CMAX], Q[CMAX], N;
double D[NMAX];
double C[NMAX][2*NMAX], Xs[NMAX], Ys[NMAX], Xa[NMAX], Ya[NMAX], Cm, Max;
int cup[CMAX];

void flux(int sursa, double crit)
{
        int p1 = 0, p2 = 1, i, j, nod, tata[CMAX], tip[CMAX];
        double min;

        for (i = 0; i < NMAX; i++)
            D[i] = INF;
        for (i = 0; i < CMAX; i++)
            InQ[i] = tip[i] = tata[i] = 0;

        Q[p1] = sursa;
        D[ sursa ] = 0;
        InQ[ sursa ] = 1;

        while (p1 != ((p2+1)&(CMAX-1)))
        {
                nod = Q[p1];
                
                if (nod <= N)
                {
                   for (i = N+1; i <= 2*N; i++)
                       if ((C[nod][i] <= crit) && (F[nod][i] == 0) && (D[i] > D[nod]+C[nod][i]))
                       {
                                D[i] = D[nod]+C[nod][i];
                                tata[i] = nod;
                                if (!InQ[i])
                                {
                                        InQ[i] = 1;
                                        Q[p2] = i;
                                        p2 = (p2+1)&(CMAX-1);
                                }
                       }
                }
                else
                {
                        if ((C[cup[nod]][nod] <= crit) && (cup[nod] > 0) && (D[cup[nod]] > D[nod]-C[cup[nod]][nod]))
                        {
                                D[cup[nod]] = D[nod]-C[cup[nod]][nod];
                                tata[cup[nod]] = nod;
                                tip[cup[nod]] = 1;
                                if (!InQ[cup[nod]])
                                {
                                        InQ[cup[nod]] = 1;
                                        Q[p2] = cup[nod];
                                        p2 = (p2+1)&(CMAX-1);
                                }
                        }
                }
                InQ[nod] = 0;
                p1 = (p1+1)&(CMAX-1);
        }

        j = 0;
        min = INF;
        for (i = N+1; i <= 2*N; i++)
            if (cup[i] == 0 && min > D[i]) j = i, min = D[i];

        Cm += min;

        while (tata[j] > 0)
        {
                if (tip[j] == 0)
                {
                        F[tata[j]][j]++;
                        cup[j] = tata[j];
                }
                else
                    F[j][tata[j]]--;
                    
                j = tata[j];
        }
        
}

int main()
{
        int i, j, nod;
        double lo, hi, mid;

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

     freopen("adapost.out", "w", stdout);
        printf("1000 1000\n", Max/1000000.0, Cm);

        for (i = 1; i <= N; i++)
            scanf("%lf %lf", Xs+i, Ys+i);
        for (i = 1; i <= N; i++)
            scanf("%lf %lf", Xa+i, Ya+i);

        for (i = 1; i <= N; i++)
            for (j = 1; j <= N; j++)
                C[i][N+j] = sqrt((Xa[j]-Xs[i])*(Xa[j]-Xs[i])+(Ya[j]-Ys[i])*(Ya[j]-Ys[i]));

        lo = 0; hi = 2000000001;
        while (hi-lo >= 0)
        {
                mid = (hi+lo)/2.0;
                Cm = 0;
                memset(F, 0, sizeof(F));
                memset(cup, 0, sizeof(cup));
                for (i = 1; i <= N && Cm < INF; i++) flux(i, mid/1000000.0);
                if (Cm >= INF) lo = mid+1;
                else hi = mid-1, Max = mid;
        }

        memset(F, 0, sizeof(F));
        memset(cup, 0, sizeof(cup));
        Cm = 0;
        for (i = 1; i <= N; i++) flux(i, Max/1000000.0);

        freopen("adapost.out", "w", stdout);
        printf("%lf %lf\n", Max/1000000.0, Cm);

        return 0;
        
}