Cod sursa(job #580880)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 13 aprilie 2011 16:42:54
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

const int N = 1000;

bool viz[N], inq[N];

queue <int> Q;

const int INF = 1000000000;

vector <int> L[N];

int sol, S, D, n, dis[N], tata[N], l_pair[N], r_pair[N], flux[N][N], cost[N][N], cap[N][N];

double sx[N], sy[N], bx[N], by[N];

void read() {
  freopen("adapost.in", "r", stdin);
  freopen("adapost.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++ i)
    scanf("%lf %lf", &sx[i], &sy[i]);
  for (int j = 1; j <= n; ++ j)
    scanf("%lf %lf", &bx[j], &by[j]);
}

double dist(double x1, double y1, double x2, double y2) {
  return (double)sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

void init() {
  S = 0;
  D = 2 * n + 1;

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

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

  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j) {
      L[i].push_back(n + j);
      L[n + j].push_back(i);
      cost[i][n + j] = dist(sx[i], sy[i], bx[j], by[j]) * 10000;
      cost[n + j][i] = - cost[i][n + j];
      cap[i][n + j] = 1;
    }
}

bool cupleaza(int nod, int val) {
  if (viz[nod])
    return 0;
  viz[nod] = 1;

  for (int j = 0; j < L[nod].size(); ++ j)
    if (cost[nod][L[nod][j]] <= val && (! r_pair[L[nod][j]]) && L[nod][j] != S) {
      l_pair[nod] = L[nod][j];
      r_pair[L[nod][j]] = nod;
      return 1;
    }

  for (int j = 0; j < L[nod].size(); ++ j)
    if (cost[nod][L[nod][j]] <= val && r_pair[L[nod][j]] && cupleaza(r_pair[L[nod][j]], val) && L[nod][j] != S) {
      l_pair[nod] = L[nod][j];
      r_pair[L[nod][j]] = nod;
      return 1;
    }

  return 0;
}

void reset() {
  for (int i = 0; i < N; ++ i)
    viz[i] = 0;
}

void hard_reset() {
  for (int i = 0; i < N; ++ i)
    l_pair[i] = r_pair[i] = 0;
}

int cuplaj(int val) {
  bool ok = true;
  int pairs = 0;
  hard_reset();

  while(ok) {
    reset();
    ok = false;

    for (int i = 1; i <= n; ++ i)
      if ((! l_pair[i]) && cupleaza(i, val)) {
        ++ pairs;
        ok = true;
      }
  }

  return pairs;
}

int cautb() {
  int i = 0, pas = 1 << 20;
  for (i = 0; pas; pas >>= 1)
    if (cuplaj(i + pas) < n)
      i += pas;
  return i + 1;
}

void reset_BF() {
  for (int i = 0; i < N; ++ i) {
    dis[i] = INF;
    inq[i] = 0;
    tata[i] = 0;
  }
}

bool BF(int val) {
  int nodc = 0;

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

  while (! Q.empty()) {
    nodc = Q.front();
    Q.pop();
    if (nodc == D)
      continue;

    for (int j = 0; j < L[nodc].size(); ++ j)
      if (cost[nodc][L[nodc][j]] <= val && dis[nodc] + cost[nodc][L[nodc][j]] < dis[L[nodc][j]] && flux[nodc][L[nodc][j]] < cap[nodc][L[nodc][j]]) {
        dis[L[nodc][j]] = dis[nodc] + cost[nodc][L[nodc][j]];
        tata[L[nodc][j]] = nodc;
        if (! inq[L[nodc][j]]) {
          Q.push(L[nodc][j]);
          inq[L[nodc][j]] = 1;
        }
      }
  }

  if (dis[D] != INF) {
    int deprop = INF;
    for (int i = D; i != S; i = tata[i])
      if (cap[tata[i]][i] - flux[tata[i]][i] < deprop)
        deprop = cap[tata[i]][i] - flux[tata[i]][i];
    for (int i = D; i != S; i = tata[i]) {
      flux[tata[i]][i] += deprop;
      flux[i][tata[i]] -= deprop;
    }
    sol += deprop * dis[D];
  }

  return (dis[D] != INF);
}

int fmcm(int d) {
  while (BF(d));
  return sol;
}

int main() {
  read();
  init();
  int d = cautb();
  printf("%lf ", (double)d / 10000.00);
  printf("%lf\n", (double)fmcm(d) / 10000.00);
  return 0;
}