Cod sursa(job #1666492)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 martie 2016 02:31:56
Problema Adapost Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 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];
char flow[2*N][2*N];
int f[2*N], n, fsum;
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 bellman() {
   int i, j;
   memset(inque, 0, sizeof(inque));
   memset(f, 0, sizeof(f));
   while(!q.empty()) q.pop();
   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();
      if(i == 2*n+1) return 1;
      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);
               }
            }
         }
      }0;
   }
   return f[2*n+1];
}

void getFlow() {
   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];
      getFlow();
      if(fsum == n) 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());
   i = bins();
   cmax = dlist[i];
   getFlow();
   out << fixed << setprecision(10) << cmax << ' ' << csum << '\n';
   return 0;
}