Cod sursa(job #2798604)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:45:55
Problema Adapost Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.49 kb
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

#define ITERATOR vector <short int>::iterator

const int NMAX = 405, INF = 2e9;
const double eps = 1.e-3;

vector <short int> graph[NMAX * 2], matchGraph[NMAX];

pair <double, double> soldat[NMAX], adapost[NMAX];

int SOURCE, DEST;
int n, gauche[NMAX], droit[NMAX], cap[NMAX * 2][NMAX * 2], flow[NMAX * 2][NMAX * 2], dad[NMAX * 2];
bool vis[NMAX * 2];
float lim, mid, dist[NMAX][NMAX], dmin[NMAX * 2], cost[NMAX * 2][NMAX * 2];

bool pairUp (int node) {
    if(vis[node])
        return 0;

    vis[node] = 1;
    for(ITERATOR it = matchGraph[node].begin(); it != matchGraph[node].end(); ++ it) {
        if(dist[node][*it] > mid)
            continue;

        if(!gauche[*it] || pairUp(gauche[*it])) {
            gauche[*it] = node;
            droit[node] = *it;
            return 1;
        }
    }

    return 0;
}

int cuplaj () {
    int i, j, ans, change;

    for(i = 1; i <= n; ++ i) {
        matchGraph[i].clear();
        gauche[i] = droit[i] = 0;
    }

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            if(dist[i][j] < mid)
                matchGraph[i].push_back(j);

    change = 1;
    while(change) {
        change = 0;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; ++ i)
            if(!droit[i] && pairUp(i))
                change = 1;
    }

    ans = 0;
    for(i = 1; i <= n; ++ i)
        if(droit[i])
            ++ ans;
    return ans;
}

double bs (double left, double right) {
    double last;
    int step;

    for(step = 1; step <= 60; ++ step) {
        mid = (left + right) * 0.5;

        if(cuplaj() == n) {
            last = mid;
            right = mid;
        }
        else
            left = mid;
    }

    return last;
}

double sqr (double x) {
    return x * x;
}

void drawEdge (int a, int b, double costAB) {
    graph[a].push_back(b);
    graph[b].push_back(a);

    cap[a][b] = 1;

    cost[a][b] = costAB;
    cost[b][a] = -costAB;
}

void buildGraph () {
    int i, j;

    SOURCE = 0;
    DEST = 2 * n + 1;
    for(i = 1; i <= n; ++ i)
        drawEdge(SOURCE, i, 0);

    for(i = 1; i <= n; ++ i)
        for(j = n + 1; j <= 2 * n; ++ j)
            if(dist[i][j - n] <= lim)
                drawEdge(i, j, dist[i][j - n]);

    for(i = n + 1; i <= 2 * n; ++ i)
        drawEdge(i, DEST, 0);
}

bool bellmanFord() {
    queue <int> q;
    int node, i;
    ITERATOR it;

    for(i = SOURCE; i <= DEST; ++ i) {
        dmin[i] = INF - eps;
        vis[i] = dad[i] = 0;
    }

    q.push(SOURCE);
    vis[SOURCE] = 1;
    dmin[SOURCE] = 0;
    while(!q.empty()) {
        node = q.front();
        q.pop();
        vis[node] = 0;
        if(node == DEST)
           continue;

        for(it = graph[node].begin(); it != graph[node].end(); ++ it)
            if(flow[node][*it] < cap[node][*it] && dmin[node] + cost[node][*it] < dmin[*it]) {
                dmin[*it] = dmin[node] + cost[node][*it];
                dad[*it] = node;

                if(!vis[*it]) {
                    q.push(*it);
                    vis[*it] = 1;
                }
            }
    }

    return dmin[DEST] < INF - eps;
}

double maxFlow() {
    ITERATOR it;
    int minFlow, node;
    double ans;

    ans = 0;
    while(bellmanFord()) {
        node = DEST;
        minFlow = INF;
        while(node != SOURCE) {
            minFlow = min(minFlow, cap[dad[node]][node] - flow[dad[node]][node]);
            node = dad[node];
        }

        node = DEST;
        while(node != SOURCE) {
            flow[dad[node]][node] += minFlow;
            flow[node][dad[node]] -= minFlow;

            node = dad[node];
        }

        ans += minFlow * dmin[DEST];
    }
    return ans;
}


int main() {
    freopen("adapost.in", "r", stdin);
    freopen("adapost.out", "w", stdout);
    int i, j;

    scanf("%d", &n);
    for(i = 1; i <= n; ++ i)
        scanf("%lf%lf", &soldat[i].first, &soldat[i].second);
    for(i = 1; i <= n; ++ i)
        scanf("%lf%lf", &adapost[i].first, &adapost[i].second);

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            dist[i][j] = sqrt(sqr(soldat[i].first - adapost[j].first) + sqr(soldat[i].second - adapost[j].second));

    lim = bs(0, 5000);

    buildGraph();

    printf("%lf %lf\n", lim, maxFlow());
    return 0;
}