Cod sursa(job #2476312)

Utilizator PetyAlexandru Peticaru Pety Data 18 octombrie 2019 17:23:57
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.09 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;
}