Cod sursa(job #1518992)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 6 noiembrie 2015 17:51:37
Problema Adapost Scor 11
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <cstring>

#define DIM (400 + 5)
#define INF (1 << 30)

using namespace std;

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

int n;

int source, destination;

double solution;

pair<double, double> soldiers[DIM], shelters[DIM];

vector<int> L[DIM];

double capacity[2 * DIM][2 * DIM], cost[2 * DIM][2 * DIM], flux[2 * DIM][2 * DIM];

int parent[2 * DIM];

double d[2 * DIM];

double Distance(int x, int y) {

    return sqrt((soldiers[x].first - shelters[y].first)  * (soldiers[x].first - shelters[y].first) + (soldiers[x].second - shelters[y].second)  * (soldiers[x].second - shelters[y].second));

}

bool BF() {

    queue<int> Q;

    for (int i = source; i <= destination; i++) {

        parent[i] = 0;
        d[i] = INF;

    }

    parent[source] = -1;
    d[source] = 0;

    Q.push(source);

    while (Q.size()) {

        int node = Q.front();

        Q.pop();

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

            int child = L[node][i];
            double C = cost[node][child];

            if (capacity[node][child] > flux[node][child] && d[node] + C < d[child]) {

                d[child] = d[node] + C;
                parent[child] = node;

                Q.push(child);

            }


        }

    }

    return (d[destination] != INF);

}

bool verif(double dist) {

    source = 0, destination = 2 * n + 1;

    memset(flux, 0, sizeof flux);
    memset(cost, 0, sizeof cost);
    memset(capacity, 0, sizeof capacity);

    for (int i = source; i <= destination; i++)
        L[i].clear();

    solution = 0;

    for (int i = 1; i <= n; i++) {

        L[source].push_back(i);
        L[i].push_back(source);

        capacity[source][i] = 1;

        L[i + n].push_back(destination);
        L[destination].push_back(i + n);

        capacity[i + n][destination] = 1;

    }

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            if ( Distance(i, j) - dist < 0.000001) {

                L[i].push_back(j + n);
                L[j + n].push_back(i);

                capacity[i][j + n] = 1;

                cost[i][j + n] = Distance(i, j);
                cost[j + n][i] = -Distance(i, j);

            }

        }

    }

    int maxflow = 0;

    while (BF()) {

        int var = parent[destination];

        if (capacity[var][destination] <= flux[var][destination])
            continue;


        double minim = capacity[var][destination] - flux[var][destination];

        while (parent[var] != -1){

            minim = min(minim, capacity[parent[var]][var] - flux[parent[var]][var]);

            var = parent[var];

        }

        var = parent[destination];
        flux[var][destination] += minim;
        flux[destination][var] -= minim;

        while (parent[var] != -1){

            flux[parent[var]][var] += minim;
            flux[var][parent[var]] -= minim;

            var = parent[var];

        }

        solution += d[destination] * minim;
        maxflow += minim;

    }

    return(maxflow == n);

}

void binarySearch() {

    double left = 0, right = 2000000;

    while(left <= right) {

        double middle = (left + right) / 2;

        if(verif(middle))
            right = middle - 0.00001;
        else
            left = middle + 0.00001;

    }

    verif(left);

    fout << setprecision(6) << fixed;
    fout << left << " " << solution << "\n";

}

int main () {

    fin >> n;

    for (int i = 1; i <= n; i++)
         fin >> soldiers[i].first >> soldiers[i].second;

    for (int i = 1; i <= n; i++)
         fin >> shelters[i].first >> shelters[i].second;

    binarySearch();

    return 0;

}

//Miriam e tare!