Cod sursa(job #2628857)

Utilizator betybety bety bety Data 17 iunie 2020 19:13:05
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.47 kb

#include <bits/stdc++.h>

#pragma GCC optimize ("O3")





using namespace std;



ifstream fin ("adapost.in");

ofstream fout ("adapost.out");



int st[802], dr[802], viz[802];

int n, S, D;

struct nod {

  double x, y;

} v[802];

double cost[802][802];

int c[802][802];

vector<int>G[802];

vector<pair<double, pair<int, int> > >E;



void addEdge (int x, int y, int flow, double cst) {

  G[x].push_back(y);

  G[y].push_back(x);

  c[x][y] += flow;

  cost[x][y] += cst;

  cost[y][x] -= cst;

}



double nush[802], d[802], nush2[802], ans;

int in[802], p[802], flux;





struct cmp {

  bool operator() (int x, int y) {

    return d[x] > d[y];

  }

};



priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;





bool dijkstra () {

  for (int i = 0; i <= n; i++)

    d[i] = nush2[i] = 1000000000;

  d[S] = 0; nush2[S] = 0;

  pq.push({d[S], S});

  while (!pq.empty()) {

    int nod = pq.top().second;

    double lol = pq.top().first;

    pq.pop();

    if (d[nod] != lol)

      continue;

    for (auto it: G[nod]) {

      if (c[nod][it]) {

        double nush3 = d[nod] + cost[nod][it] - nush[it] + nush[nod];

        if (nush3 < d[it]) {

          d[it] = nush3;

          nush2[it] = nush2[nod] + cost[nod][it];

          p[it] = nod;

          pq.push({d[it], it});

        }

      }

    }

  }

  memcpy(nush, nush2, sizeof(nush));

  if (nush[D] == 1000000000)

    return 0;

  return 1;

}





void bellman_ford () {

  queue<int>q;

  for (int i = 0; i <= n; i++)

    nush[i] = 1000000000;

  nush[S] = 0;

  q.push(S);

  in[S] = 1;

  while (!q.empty()) {

    int u = q.front();

    in[u] = 0;

    q.pop();

    for (auto it: G[u]) {

      if (c[u][it]) {

        if (nush[u] + cost[u][it] < nush[it]) {

          nush[it] = nush[u] + cost[u][it];

          if (!in[it]) {

            in[it] = 1;

            q.push(it);

          }

        }

      }

    }

  }

}



bool cuplaj (int x) {

  if (viz[x])

    return 0;

  viz[x] = 1;

  for (int i = 0; i < G[x].size(); i++) {

    int v = G[x][i];

    if (!dr[v]) {

      st[x] = v;

      dr[v] = x;

      return 1;

    }

  }

  for (int i = 0; i < G[x].size(); i++) {

    int v = G[x][i];

    if (cuplaj(dr[v])) {

      st[x] = v;

      dr[v] = x;

      return 1;

    }

  }

  return 0;

}



bool ok (int t) {

  for (int i = 0; i <= 2 * n + 1; i++)

    G[i].clear();

  memset(st, 0, sizeof(st));

  memset(dr, 0, sizeof(dr));

  memset(viz, 0, sizeof(viz));

  for (int i = 0; i <= t; i++) {

    G[E[i].second.first].push_back(E[i].second.second);

  }

  int ans = 0;

  bool ok = 1;

  while (ok) {

    ok = 0;

    memset(viz, 0, sizeof(viz));

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

      if (!st[i])

        if (cuplaj(i)) {

          ok = 1;

          ans++;

        }

    }

  }

  return (ans == n);

}



int main()

{

  fin >> n;

  S = 0; D = 2 * n + 1;

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

    fin >> v[i].x >> v[i].y;

  }

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

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

    E.push_back({sqrt((v[i].x - v[j + n].x) * (v[i].x - v[j + n].x) + (v[i].y - v[j + n].y) * (v[i].y - v[j + n].y)), {i, j}});

  }

  sort(E.begin(), E.end());

  int st = 0, dr = E.size() - 1, k;

  while (st <= dr) {

    int mij = (st + dr) / 2;

    if (ok(mij)){

      k = mij;

      dr = mij - 1;

    }

    else

      st = mij + 1;

  }

  fout << fixed << setprecision(5) << E[k].first << " ";

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

    addEdge(S, i, 1, 0);

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

    addEdge(i + n, D, 1, 0);

  for (int i = 0; i <= k; i++) {

    addEdge(E[i].second.first, E[i].second.second + n, 1, E[i].first);

  }

  n = 2 * n + 1;

  bellman_ford();

  while (dijkstra()) {

    int fmin = 1000000000;

    double cst = 0;

    for (int nod = D; nod != S; nod = p[nod]) {

      fmin = min (fmin, c[p[nod]][nod]);

      cst += cost[p[nod]][nod];

    }

    flux += fmin;

    ans += fmin * nush2[D];

    for (int nod = D; nod != S; nod = p[nod]) {

      c[p[nod]][nod] -= fmin;

      c[nod][p[nod]] += fmin;

    }

  }

  fout << fixed << setprecision(5) << ans;

  return 0;

}