Cod sursa(job #2932934)

Utilizator ptudortudor P ptudor Data 4 noiembrie 2022 12:06:40
Problema Adapost Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <bits/stdc++.h>
using namespace std;


#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("adapost.in");
ofstream out("adapost.out");
#endif

const int nmax = 405;
int n,cap[nmax][nmax];
double cost[nmax][nmax];
int flow[nmax][nmax];
pair<double,double>sold[nmax],adap[nmax];

vector<vector<pair<int,double>>> g;
double square(double a) {
    return a * a;
}
double dist2(pair<double,double> a, pair<double,double> b) {
    return sqrt(square(a.first - b.first) + square(a.second - b.second));
}


const int inf = 1000000005;
double find_augmenting_path() {
    priority_queue<pair<double,int>> q;
    q.push({0 , 0});
    vector<double> myDis(2 * n + 2, inf);
    myDis[0] = 0;

    vector<int> path(2 * n + 2,  0);
    while(!q.empty()) {
        double val = -q.top().first;
        int node = q.top().second;
        q.pop();

        if (val > myDis[node]) continue;

        for (auto k : g[node]) {
            double costEdge =  cost[node][k.first];

            if (myDis[k.first] > myDis[node] + costEdge && flow[node][k.first] < cap[node][k.first]) {
                myDis[k.first] = myDis[node] + costEdge;
                path[k.first] = node;
                q.push({-myDis[k.first], k.first});
            }
        }
    }

    if (path[2 * n + 1] == 0) {
        return -1;
    }


    int node = 2 * n + 1,bottle_neck = inf;

    while(node != 0) {
        int from = path[node];
        bottle_neck = min(bottle_neck , cap[from][node] - flow[from][node]);
        node = from;
    }

    node = 2 * n + 1;

    double cur_cost = 0;
    while(node != 0) {
        int from = path[node];
        flow[from][node] += bottle_neck;
        flow[node][from] -= bottle_neck;
        cur_cost += cost[from][node];
        node = from;
    }

    return cur_cost;
}
double maxflow() {
    double total_cost = 0;

    while(true) {
        double added_cost = find_augmenting_path();
        if (added_cost == -1) {
            return total_cost;
        }

        total_cost += added_cost;
    }

    return total_cost;
}
int main() {
    in >> n;
    g.resize(2 * n + 2);
    for (int i =1 ; i <= n; i++) {
        in >> sold[i].first >> sold[i].second;
    }   

    for (int i =1 ; i <= n; i++) {
        in >> adap[i].first >> adap[i].second;
    }   

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            double ds = dist2(sold[i], adap[j]);
            g[i].push_back({j + n, ds});
            g[j + n].push_back({i, -ds});
            cost[i][j + n] = ds;
            cost[j + n][i] = -ds;
            cap[i][j + n] = 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        g[0].push_back({i, 0});
        g[i].push_back({0, 0});
        cap[0][i] = 1;
    }

    for (int i = n + 1; i <= n * 2; i++) {
        cap[i][2 * n + 1] = 1;
        g[i].push_back({2 * n + 1, 0});
        g[2 * n + 1].push_back({i, 0});
    }


    double maxval = maxflow();
    
    double maxedge = -inf;
    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= 2 * n; j++) {
            if (flow[i][j] == 1) {
                maxedge = max(maxedge , cost[i][j]);
            }
        }
    }

    out << fixed << setprecision(6) << maxedge << " " << maxval << "\n";
}