Cod sursa(job #1760639)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 21 septembrie 2016 03:20:01
Problema Adapost Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <bits/stdc++.h>

#define x first
#define y second
#define INF 1000000

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

int capacity[1024][1024], F[1024][1024], N, T[1024], flux;
double solution, mainSolution, cost[1024][1024], D[1024], stanga = 1000000, dreapta;
pair< double,  double> soldat[1024], adapost[1024];
bitset<1024>v;

vector <int> L[1024];
queue  <int> Q;

bool BF(double maxMuchie)
{
    for(int i = 0; i <= 2 * N; i ++)
    {
        D[i] = INF;
        v[i] = 0;
    }

    D[0] = 0;
    D[808] = INF;
    v[808] = 0;
    Q.push(0);

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

        for(int i = 0; i < L[node].size(); i ++)
        {
            int neighbour = L[node][i];

            if( ( capacity[node][neighbour] > F[node][neighbour] ) && (cost[node][neighbour] <= maxMuchie) )
            {
                D[neighbour] = D[node] + cost[node][neighbour];
                T[neighbour] = node;

                if(v[neighbour] == 0)
                {
                    Q.push(neighbour);
                    v[neighbour] = 1;
                }
            }

        }
    }

    return D[808] != INF ? true : false;

}

bool cuplaj( double maxMuchie)
{
    solution = 0;
    flux = 0;
    while( BF(maxMuchie) )
    {
        int x = 808;
        int minFlux = INF;

        while(x != 0)
        {
            minFlux = min( minFlux, capacity[ T[x] ][x] - F[ T[x] ][x] );
            x = T[x];
        }

        x = 808;

        while(x != 0)
        {
            solution += minFlux * cost[ T[x] ][x];
            F[ T[x] ][x] += minFlux;
            F[x][ T[x] ] -= minFlux;
            x = T[x];
        }
        flux += minFlux;
    }

    memset(F, 0, sizeof(F));

    return solution != 0 && flux == N ? true : false;
}


int main()
{
    fin >> N;

    for(int i = 1; i <= N; i ++)
    {
        fin >> soldat[i].x >> soldat[i].y;
    }

    for(int i = 1; i <= N; i ++)
    {
        fin >> adapost[i].x >> adapost[i].y;
    }

    for(int i = 1; i <= N; i ++)
    {
        L[0].push_back(i);
        L[i].push_back(0);
        capacity[0][i] = 1;

        L[808].push_back(N + i);
        L[N + i].push_back(808);
        capacity[N + i][808] = 1;


        for(int j = 1; j <= N; j ++)
        {
            double dist = sqrt( (adapost[j].y - soldat[i].y) * (adapost[j].y - soldat[i].y) +
                                (adapost[j].x - soldat[i].x) * (adapost[j].x - soldat[i].x) );

            if(dist > dreapta)
            {
                dreapta = dist;
            }
            if(dist < stanga)
            {
                stanga = dist;
            }
            L[i].push_back(N + j);
            capacity[i][N + j] = 1;
            cost[i][N + j] = dist;
            cost[N + j][i] = -dist;
        }
    }

    while(stanga <= dreapta)
    {
        double middle = (stanga + dreapta) / 2;

        if(cuplaj(middle))
        {
            dreapta = middle - 0.0001;
            mainSolution = solution;
        }
        else
        {
            stanga = middle + 0.0001;
        }
    }

    fout << dreapta << " " << mainSolution;


    return 0;
}