Cod sursa(job #953082)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:57:39
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.53 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
  
#define inf 1e10
#define pb push_back
#define nmax 512
  
using namespace std;
  
double sx[2 * nmax],sy[2 * nmax],dist[nmax * nmax],di[2 * nmax];
double cost[2 * nmax][2 * nmax],maxdist;
int coada[nmax * nmax],start,final;
char v[2 * nmax];
short int fl[2 * nmax][2 * nmax],cap[2 * nmax][2 * nmax];
int cuplat[2 * nmax],prev[2 * nmax];
int i,j,n,p;
vector <int> e[2 * nmax];
  
inline double sqr(double x) {
    return x * x;
}
  
double d(int i,int j) {
    return sqrt(sqr(sx[i] - sx[j]) + sqr(sy[i] - sy[j]));
}
  
int cupleaza(int x) {
    if(v[x]) return 0;
    v[x] = 1;
    int sx;
    if(x <= n) sx = n + 1;
    else sx = 1;
    for(int i = sx; i < sx + n; i++) {
        if(fabs(cost[x][i]) <= maxdist && (!cuplat[i] || cupleaza(cuplat[i]))) {
            cuplat[x] = i;
            cuplat[i] = x;
            return 1;
        }
    }
    return 0;
}
  
int cupl(int x) {
    maxdist = dist[x];
    memset(v,0,sizeof(v));
    memset(cuplat,0,sizeof(cuplat));
    for(int i = 1; i <= n; i++)
        if(!cuplat[i] && !cupleaza(i)) {
                memset(v,0,sizeof(v));
                cupleaza(i);
            }
    int r = 0;
    for(int i = 1; i <= n; i++) if(cuplat[i]) r++;
    return r;
}
  
int cauta(int f,int l) {
    int r = 0;
    while(f <= l) {
        int m = (f + l) / 2;
        if(cupl(m) == n) {
            l = m - 1;
            r = m;
        }
        else f = m + 1;
    }
    return r;
}
  
void capacities() {
    for(int i = n + 1; i <= 2 * n; i++) {
        e[i].pb(2 * n + 1);
        e[2 * n + 1].pb(i);
        cap[i][2 * n + 1] = 1;
    }
    for(int i = 1; i <= n; i++) {
        cap[0][i] = 1;
        e[0].pb(i);
        for(int j = n + 1; j <= 2 * n; j++)
        if(cost[i][j] <= maxdist) {
            e[i].pb(j);
            e[j].pb(i);
            cap[i][j] = 1;
        }
    }
}
  
int drum() {
    for(int i = 0; i <= 2 * n + 1; i++) {
        di[i] = inf;
        prev[i] = -1;
    }
    di[0] = 0;
    final = 0;
    start = 1;
    coada[++final] = 0;
    v[0] = 1;
    while(final >= start) {
        int nod = coada[start];
        start++;
        for(int i = 0; i < (int)e[nod].size(); i++) {
            int nn = e[nod][i];
            if(cap[nod][nn] > fl[nod][nn]) {
                double nd = di[nod] + cost[nod][nn];
                if(di[nn] > nd) {
                    di[nn] = nd;
                    prev[nn] = nod;
                    if(!v[nn]) coada[++final] = nn;
                    v[nn] = 1;
                }
            }
        }
        v[nod] = 0;
    }
    if(di[2 * n + 1] == inf) return 0;
    else {
        int x = 2 * n + 1;
        int minim = 100;
        while(prev[x] != -1) {
            if(cap[prev[x]][x] - fl[prev[x]][x] < minim)
                minim = cap[prev[x]][x] - fl[prev[x]][x];
            x = prev[x];
        }
        x = 2 * n + 1;
        while(prev[x] != -1) {
            fl[prev[x]][x] += minim;
            fl[x][prev[x]] -= minim;
            x = prev[x];
        }
        return 1;
    }
}
  
void greedy() {
    for(int i = 1; i <= n; i++) {
        int care = 0;
        double minim = inf;
        for(int j = n + 1; j < 2 * n + 1; j++)
            if(cost[i][j] < minim) {
                minim = cost[i][j];
                care = j;
            }
        int j = care;
        if(cap[0][i] > fl[0][i] &&
           cap[i][j] > fl[i][j] &&
           cap[j][2 * n + 1] > fl[j][2 * n + 1]) {
                fl[0][i]++; fl[i][0]--;
                fl[i][j]++; fl[j][i]--;
                fl[j][2 * n + 1]++; fl[2 * n + 1][j]--;
        }
    }
}
  
void flux() {
    capacities();
    greedy();
    memset(v,0,sizeof(v));
    while(drum()) ;
    double r = 0;
    for(int i = 1; i <= n; i++)
        for(int j = n + 1; j <= 2 * n; j++)
            r += fl[i][j] * cost[i][j];
    printf("%lf\n",r);
}
  
int main() {
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
      
    scanf("%d",&n);
    for(int i = 1; i <= 2 * n; i++) scanf("%lf%lf",&sx[i],&sy[i]);
    for(int i = 1; i <= n; i++)
        for(int j = n + 1; j <= 2 * n; j++) {
            cost[i][j] = d(i,j);
            cost[j][i] = - cost[i][j];
            dist[++p] = cost[i][j];
        }
  
    sort(dist + 1,dist + p + 1);
    int x = cauta(1,p);
    maxdist = dist[x];
    printf("%lf ",dist[x]);
  
    flux();
  
    return 0;
}