Cod sursa(job #1666497)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 martie 2016 02:50:40
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("adapost.in");
ofstream out("adapost.out");

const int N = 405;
const int INF = 1e9;
const double eps = 1e-7;

pair<double, double> sld[N], shl[N];
vector<double> dlist;
double cost[2*N][2*N], dist[2*N], cbest, cmax, csum, dbest;
bool inque[2*N], cap[2*N][2*N], vis[N];
char flow[2*N][2*N];
int f[2*N], n, fsum, l[N], r[N];
queue<int> q;

inline int cmp(double a, double b) {
   if (a-b < -eps) return -1;
   if (a-b > eps) return 1;
   return 0;
}

bool pair_up(int x) {
   if(vis[x]) return 0;
   vis[x] = 1;
   for(int i = 1; i <= n; i++) {
      if(cmp(cost[x][n+i], cmax) <= 0 && !r[i]) {
         r[i] = x;
         l[x] = i;
         return 1;
      }
   }
   for(int i = 1; i <= n; i++) {
      if(cmp(cost[x][n+i], cmax) <= 0 && pair_up(r[i])) {
         r[i] = x;
         l[x] = i;
         return 1;
      }
   }
   return 0;
}

bool max_match() {
   memset(l, 0, sizeof(l));
   memset(r, 0, sizeof(r));
   bool done;
   do {
      done = 1;
      memset(vis, 0, sizeof(vis));
      for(int i = 1; i <= n; i++) {
         if(!l[i]) {
            if(pair_up(i)) done = 0;
            else return 0;
         }
      }
   } while(!done);
   for(int i = 1; i <= n; i++) {
      if(!l[i]) return 0;
   }
   return 1;
}

bool bellman() {
   int i, j;
   memset(inque, 0, sizeof(inque));
   memset(f, 0, sizeof(f));
   for(i = 1; i <= 2*n+1; i++) dist[i] = INF;
   inque[0] = 1;
   dist[0] = 0;
   q.push(0);
   while(!q.empty()) {
      i = q.front();
      inque[i] = 0;
      q.pop();
      for(j = 0; j <= 2*n+1; j++) {
         if(flow[i][j] < cap[i][j] && cmp(cost[i][j], cmax) <= 0) {
            if(cmp(dist[j], dist[i] + cost[i][j]) > 0) {
               dist[j] = dist[i] + cost[i][j];
               f[j] = i;
               if(!inque[j]) {
                  inque[j] = 1;
                  q.push(j);
               }
            }
         }
      }
   }
   return f[2*n+1];
}

void get_flow() {
   memset(flow, 0, sizeof(flow[0][0])*N*N);
   csum = fsum = 0;
   while(bellman()) {
      for(int i = 2*n+1; i != 0; i = f[i]) {
         flow[f[i]][i]++;
         flow[i][f[i]]--;
         csum += cost[f[i]][i];
      }
      fsum++;
   }
}

int bins() {
   int lo = 0, hi = n*n, med;
   while(lo <= hi) {
      med = (lo+hi)>>1;
      cmax = dlist[med];
      if(max_match()) hi = med-1;
      else lo = med+1;
   }
   return hi+1;
}

int main() {
   int i, j;
   double x, y, d;
   in >> n;
   for(i = 1; i <= n; i++) {
      in >> x >> y;
      sld[i] = make_pair(x, y);
   }
   for(i = 1; i <= n; i++) {
      in >> x >> y;
      shl[i] = make_pair(x, y);
   }
   for(i = 1; i <= n; i++) {
      cap[0][i] = 1;
      cap[i+n][2*n+1] = 1;
      for(j = 1; j <= n; j++) {
         x = sld[i].first - shl[j].first;
         y = sld[i].second - shl[j].second;
         d = sqrt(x*x + y*y);
         dlist.push_back(d);
         cost[i][j+n] = d;
         cost[j+n][i] = -d;
         cap[i][j+n] = 1;
      }
   }
   sort(dlist.begin(), dlist.end());
   cmax = dlist[bins()];
   get_flow();
   out << fixed << setprecision(10) << cmax << ' ' << csum << '\n';
   return 0;
}