Cod sursa(job #1739202)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 8 august 2016 20:43:23
Problema Adapost Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.2 kb
/**
  *  Worg
  */
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <utility>

using namespace std;
FILE *fin = freopen("adapost.in", "r", stdin);
FILE *fout = freopen("adapost.out", "w", stdout);

const int MAX_N = 1 + 400 + 10;
const double MAX_DIST = 2000;
const double MIN_DIST = 1e-7;
const int MAX_INF = 0x3fffffff;

/*---------------------------------*/
pair< double,double > coord[MAX_N * 2];
double dist[MAX_N * 2][MAX_N * 2];
int N;
/*---------------------------------*/
int cap[MAX_N * 2][MAX_N * 2];
double cost[MAX_N * 2][MAX_N * 2];

vector< int > graph[2 * MAX_N];

bool inQueue[MAX_N * 2];
queue< int > Q;
int before[MAX_N * 2];
double dmin[MAX_N * 2];

int totalFlow;
double totalCost;
/*---------------------------------*/



double getDist(int u, int v) {
    return sqrt((coord[u].first - coord[v].first) * (coord[u].first - coord[v].first) +
                (coord[u].second - coord[v].second) * (coord[u].second - coord[v].second));
}

void readData() {
    scanf("%d", &N);
    for(int i = 1; i <= 2 * N; i++) {
        scanf("%lf%lf", &coord[i].first, &coord[i].second);
    }

    for(int i = 1; i <= N; i++) {
        for(int j = N + 1; j <= 2 * N; j++) {
            double d = getDist(i, j);
            dist[i][j] = d;
        }
    }
}

void buildGraph(double distLimit) {
    const int S = 2 * N + 1;
    const int D = 2 * N + 2;

    for(int i = 1; i <= N; i++) {
        graph[S].push_back(i); graph[i].push_back(S);
        cap[S][i] = 1; cap[i][S] = 0;
    }
    for(int i = 1; i <= N; i++) {
        for(int j = N + 1; j <= 2 * N; j++) {
            if(dist[i][j] <= distLimit) {
                graph[i].push_back(j); graph[j].push_back(i);
                cap[i][j] = 1; cap[j][i] = 0; cost[i][j] = dist[i][j]; cost[j][i] = -dist[i][j];
            }
        }
    }
    for(int i = N + 1; i <= 2 * N; i++) {
        graph[i].push_back(D); graph[D].push_back(i);
        cap[i][D] = 1; cap[D][i] = 0;
    }
}

bool bellmanFord() {
    const int S = 2 * N + 1;
    const int D = 2 * N + 2;

    for(int i = 1; i <= D; i++) {
        dmin[i] = MAX_INF;
    }
    dmin[S] = 0; Q.push(S);

    while(!Q.empty()) {
        int node = Q.front(); Q.pop(); inQueue[node] = false;
        for(vector< int >::iterator it = graph[node].begin(); it != graph[node].end(); it++) {
            if(cap[node][*it] && dmin[*it] > dmin[node] + cost[node][*it]) {
                dmin[*it] = dmin[node] + cost[node][*it];
                before[*it] = node;

                if(!inQueue[*it]) {
                    Q.push(*it); inQueue[*it] = true;
                }
            }
        }
    }

    if(dmin[D] == MAX_INF) {
        return false;
    } else {
        int flow = MAX_INF;
        for(int node = D; node != S; node = before[node]) {
            flow = min(flow, cap[before[node]][node]);
        }
        totalFlow += flow;

        for(int node = D; node != S; node = before[node]) {
            cap[before[node]][node] -= flow;
            cap[node][before[node]] += flow;
            totalCost += flow * cost[before[node]][node];
        }

        return true;
    }
}

void resetGraph() {
    for(int i = 1; i <= 2 * N + 2; i++) {
        graph[i].clear();
    }
}

bool goodFlow(double distLimit, bool reset = true) {
    buildGraph(distLimit);
    totalFlow = 0; totalCost = 0;
    while(bellmanFord());

    if(reset) {
        resetGraph();
    }

    if(totalFlow == N) {
        return true;
    } else {
        return false;
    }
}

void binarySearch() {
    double dmax = 0, dtotal = 0;


    for(double step = MAX_DIST; step > 1e-7; step *= 0.5) {
        if(!goodFlow(dmax + step)) {
            dmax += step;
        }
    }
    dmax += 1e-6;

    printf("%.6f ", dmax);
    goodFlow(dmax, false);
    for(int i = 1; i <= N; i++) {
        for(vector< int >::iterator it = graph[i].begin(); it != graph[i].end(); it++) {
            if(*it != 1 && cap[i][*it] == 0) {
                dtotal += dist[i][*it]; break;
            }
        }
    }
    printf("%.6f\n", dtotal);

}

int main() {
    readData();
    binarySearch();
    return 0;
}