Cod sursa(job #682269)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 18 februarie 2012 19:57:40
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.56 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const double eps = 0.00001;

const int INF = 2000000000;

// variabile cautb + cuplaj
const int N = 405;

int n, st[N], dr[N];

double xs[N], ys[N], xa[N], ya[N];

vector <double> v;

vector <int> L[N];

bool viz[N];

void read() {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++ i)
    scanf("%lf%lf", &xs[i], &ys[i]);

  for (int i = 1; i <= n; ++ i)
    scanf("%lf%lf", &xa[i], &ya[i]);
}

// distanta dintre doua puncte
double dist(double x1, double y1, double x2, double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

// formez vectorul cu valorile ce pot fi luate de costurile muchiilor
void init() {
  v.push_back(0);

  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
      v.push_back(dist(xs[i], ys[i], xa[j], ya[j]));

  sort(v.begin(), v.end());
}

void reset_graf() {
  for (int i = 1; i <= n; ++ i)
    L[i].clear();

  for (int i = 1; i <= n; ++ i)
    st[i] = dr[i] = 0;
}

// adaug in graf doar muchiile cu costuri < val
void make_graf(double val) {
  reset_graf();

  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
      if (dist(xs[i], ys[i], xa[j], ya[j]) < val + eps)
        L[i].push_back(j);
}

void reset(bool a[N]) {
  for (int i = 1; i <= n; ++ i)
    a[i] = 0;
}

bool pair_up(int nod) {
  if (viz[nod])
    return 0;

  viz[nod] = 1;

  for (int i = 0; i < (int)L[nod].size(); ++ i)
    if (!dr[L[nod][i]]) {
      st[nod] = L[nod][i];
      dr[L[nod][i]] = nod;
      return 1;
    }

  for (int i = 0; i < (int)L[nod].size(); ++ i)
    if (pair_up(dr[L[nod][i]])) {
      st[nod] = L[nod][i];
      dr[L[nod][i]] = nod;
      return 1;
    }

  return 0;
}

int cuplaj(double val) {
  bool ok = 1;
  int nrp = 0;

  make_graf(val);

  while (ok) {
    ok = 0;
    reset(viz);

    for (int i = 1; i <= n; ++ i)
      if (!st[i] && pair_up(i)) {
        ++ nrp;
        ok = 1;
      }
  }

  return nrp;
}

int cautb() {
  int i = 0, pas = 1;

  while ((pas << 1) < v.size())
    pas <<= 1;

  for (i = 0; pas; pas >>= 1)
    if (i + pas < (int)v.size() && cuplaj(v[i + pas]) < n)
      i += pas;

  return i + 1;
}

// variabile flux maxim de cost minim

const int NN = 2 * N;

int S, D, dad[NN], cap[NN][NN], flux[NN][NN];

double cm, dis[NN], cost[NN][NN];

bool inq[NN];

vector <int> M[NN];

struct comp {
  bool operator() (const int &a, const int &b) {
    return dis[a] > dis[b];
  }
};

priority_queue <int, vector<int>, comp> Q;

// formez graful ce contine toate muchiile cu cost < val si adaug o sursa si o destinatie virtuala
void init_flux(double val) {
  S = 0;

  for (int i = 1; i <= n; ++ i) {
    M[S].push_back(i);
    M[i].push_back(S);
    cap[S][i] = 1;
  }

  D = 2 * n + 1;

  for (int j = 1; j <= n; ++ j) {
    M[D].push_back(n + j);
    M[n + j].push_back(D);
    cap[n + j][D] = 1;
  }

  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
      if (dist(xs[i], ys[i], xa[j], ya[j]) < val + eps) {
        cost[i][n + j] = dist(xs[i], ys[i], xa[j], ya[j]);
        cap[i][n + j] = 1;
        cost[n + j][i] = - cost[i][n + j];
        M[i].push_back(n + j);
        M[n + j].push_back(i);
      }
}

void reset_BF() {
  for (int i = S; i <= D; ++ i) {
    dad[i] = - 1;
    dis[i] = INF;
    inq[i] = 0;
  }
}

bool BF() {
  int nc;

  reset_BF();

  Q.push(S);
  inq[S] = 1;
  dis[S] = 0;

  while (!Q.empty()) {
    nc = Q.top();
    inq[nc] = 0;
    Q.pop();

    for (int i = 0; i < (int)M[nc].size(); ++ i)
      if (flux[nc][M[nc][i]] < cap[nc][M[nc][i]] && dis[nc] + cost[nc][M[nc][i]] < dis[M[nc][i]]) {
        dis[M[nc][i]] = dis[nc] + cost[nc][M[nc][i]];
        dad[M[nc][i]] = nc;
        if (inq[M[nc][i]] == 0) {
          Q.push(M[nc][i]);
          inq[M[nc][i]] = 1;
        }
      }
  }

  return (dad[D] != - 1);
}

inline int min(int x, int y) {
  return x < y ? x : y;
}

// calculez fluxul maxim ce poate fi transmis pe un drum
inline void compute_flux(int &fc) {
  for (int i = D; i != S; i = dad[i])
    fc = min(cap[dad[i]][i] - flux[dad[i]][i], fc);
}

inline void propaga_flux(int fc) {
  for (int i = D; i != S; i = dad[i]) {
    flux[dad[i]][i] += fc;
    flux[i][dad[i]] -= fc;
  }
}

inline void baga_flux() {
  int fc;
  
  fc = INF;

  compute_flux(fc);
  
  cm += fc * dis[D];

  propaga_flux(fc);
}

void fmcm() {
  while (BF())
    baga_flux();
}

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

  read();

  init();

  double rez = v[cautb()];

  printf("%.6lf ", rez);

  init_flux(rez);

  fmcm();

  printf("%.6lf\n", cm);

  return 0;
}