Cod sursa(job #1519045)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 6 noiembrie 2015 18:56:02
Problema Adapost Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.13 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];

int capacity[2 * DIM][2 * DIM], flux[2 * DIM][2 * DIM];

int parent[2 * DIM];

double d[2 * DIM], cost[2 * DIM][2 * DIM];

vector<int> L[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 vis[2 * DIM];

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

        vis[node] = false;

        if(node == destination)
            continue;

        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;

                if(!vis[child])
                    Q.push(child);

                vis[child] = true;

            }

        }

    }

    return (d[destination] != INF);

}

void maxFlow(double dist) {

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

    memset(vis, false, sizeof vis);

    solution = 0;

    for (int i = 1; i <= 2 * n; i++)
        L[i].clear();

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

            }

        }

    }

    while (BF()) {

        int var = parent[destination];

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


        int 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;

    }

}

int Right[2 * DIM], Left[2 * DIM];

bool cupleaza(int node) {

    vis[node] = true;

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

        int child = L[node][i];

        if(!Right[child]) {

            Left[node] = child;
            Right[child] = node;

            return true;

        }

    }

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

        int child = L[node][i];

        if(!vis[Right[child]] && cupleaza(Right[child])) {

            Left[node] = child;
            Right[child] = node;

            return true;

        }

    }

    return false;

}

bool verif(double dist) {

   memset(Right, 0, sizeof Right);
   memset(Left, 0, sizeof Left);

   for (int i = 1; i <= 2 * n; i++)
        L[i].clear();

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

    bool ok;

    int cuplaj = 0;

    do {

        ok = false;

        memset(vis, 0, sizeof vis);

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

            if(!Left[i] && cupleaza(i)) {

                ok = true;
                cuplaj++;

            }

        }

    }while (ok);

    return (cuplaj == n);

}

void binarySearch() {

    double left = 0, right = 1500;

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

        double middle = (left + right) / 2;

        if(verif(middle))
            right = middle;
        else
            left = middle;

    }

    maxFlow(right);

    fout << setprecision(6) << fixed;
    fout << right << " " << 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!