Cod sursa(job #2798600)

Utilizator LicaMihaiIonutLica Mihai- Ionut LicaMihaiIonut Data 11 noiembrie 2021 16:42:15
Problema Adapost Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.22 kb
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cmath>

#define INF 1000000000
#define EPS 0.00001

#define MAXN 400
#define MAXK 802
#define MAXU (MAXN*MAXN)
#define MAXH 322000

double d[MAXK+1], dist[MAXK+1], cost[MAXH+1], km[MAXN+1][MAXN+1], real[MAXK+1];
double a[MAXN+1], b[MAXN+1], x[MAXN+1], y[MAXN+1];
int val[MAXU+1], next[MAXU+1], lista[MAXN+1], fata[MAXN+1], baiat[MAXN+1];
bool viz[MAXN+1], ok[MAXK+1], done[MAXK+1];
int heap[MAXK+1], poz[MAXK+1], sursa, destin, k, n, h, o;
int l[MAXK+1], e[MAXH+1], u[MAXH+1], q[10*MAXH+1], from[MAXK+1];
short int f[MAXK+1][MAXK+1], c[MAXK+1][MAXK+1];

inline int tata(int p){
    return p/2;
}

inline int fiust(int p){
    return 2*p;
}

inline int fiudr(int p){
    return 2*p+1;
}

inline void swap(int p, int q){
    int aux=heap[p];
    heap[p]=heap[q];
    heap[q]=aux;
    poz[heap[p]]=p;
    poz[heap[q]]=q;
}

inline void urcare(int p){
    while((p>1)&&(d[heap[p]]<d[heap[tata(p)]])){
        swap(p, tata(p));
        p=tata(p);
    }
}

inline void coborare(int p){
    int q;
    bool f=1;
    while((f)&&(fiust(p)<=k)){
        q=fiust(p);
        if((fiudr(p)<=k)&&(d[heap[fiudr(p)]]<d[heap[q]]))
            q=fiudr(p);
        if(d[heap[q]]<d[heap[p]]){
            swap(p, q);
            p=q;
        }else f=0;
    }
}

inline void adauga(int x, int y){
    o++;
    val[o]=y;
    next[o]=lista[x];
    lista[x]=o;
}

inline void add(int x, int y, int z, double t){
    c[x][y]=z;
    h++;
    e[h]=y;
    u[h]=l[x];
    l[x]=h;
    cost[h]=t;
}

bool gasim(int x){
    if(viz[x]) return 0;
    viz[x]=1;
    int p=lista[x];
    while(p){
        if(baiat[val[p]]==0){
            baiat[val[p]]=x;
            fata[x]=val[p];
            return 1;
        }
        p=next[p];
    }
    p=lista[x];
    while(p){
        if(gasim(baiat[val[p]])){
            baiat[val[p]]=x;
            fata[x]=val[p];
            return 1;
        }
        p=next[p];
    }
    return 0;
}

inline bool check(double lim){
    o=0;
    for(int i=1; i<=n; i++){
        fata[i]=baiat[i]=lista[i]=0;
        for(int j=1; j<=n; j++)
            if(km[i][j]<=lim)
                adauga(i, j);
    }
    bool f=1;
    while(f){
        f=0;
        memset(viz, 0, sizeof viz);
        for(int i=1; i<=n; i++)
            if(fata[i]==0)
                if(gasim(i))
                    f=1;
    }
    int p=1;
    while((p<=n)&&(fata[p])) p++;
    return p>n;
}

inline void graf(double lim){
    sursa=2*n+1;
    k=destin=2*n+2;
    for(int i=1; i<=n; i++){
        add(sursa, i, 1, 0);
        add(i, sursa, 0, 0);
        add(i+n, destin, 1, 0);
        add(destin, i+n, 0, 0);
        for(int j=1; j<=n; j++){
            if(km[i][j]<=lim+EPS){
                add(i, j+n, 1, km[i][j]);
                add(j+n, i, 0, -km[i][j]);
            }
        }
    }
}

inline void bellman(){
    int p, st, dr;
    for(int i=1; i<=k; i++)
        dist[i]=INF;
    dist[sursa]=0;
    st=0;
    dr=1;
    q[0]=sursa;
    ok[sursa]=1;
    while(st<dr){
        ok[q[st]]=0;
        p=l[q[st]];
        while(p){
            if((c[q[st]][e[p]]-f[q[st]][e[p]]>0)&&(dist[q[st]]+cost[p]<dist[e[p]])){
                dist[e[p]]=dist[q[st]]+cost[p];
                if(!ok[e[p]]){
                    ok[e[p]]=1;
                    q[dr++]=e[p];
                }
            }
            p=u[p];
        }
        st++;
    }
}

inline bool dijkstra(){
    int p, x;
    double aux;
    for(int i=1; i<=k; i++){
        d[i]=INF;
        heap[i]=i;
        poz[i]=i;
        done[i]=0;
    }
    d[sursa]=0;
    real[sursa]=0;
    urcare(poz[sursa]);
    while(d[heap[1]]<INF-100){
        x=heap[1];
        aux=d[x];
        done[x]=1;
        d[x]=INF;
        coborare(1);
        p=l[x];
        while(p){
            if((!done[e[p]])&&(c[x][e[p]]-f[x][e[p]]>0)&&(aux+cost[p]+dist[x]-dist[e[p]]<d[e[p]])){
                d[e[p]]=aux+cost[p]+dist[x]-dist[e[p]];
                real[e[p]]=real[x]+cost[p];
                from[e[p]]=x;
                urcare(poz[e[p]]);
            }
            p=u[p];
        }
        d[x]=INF;
        coborare(1);
    }
    for(int i=1; i<=k; i++)
        dist[i]=real[i];
    return done[destin];
}

inline double fmcm(){
    int x;
    double ans;
    bellman();
    while(dijkstra()){
        ans+=dist[destin];
        x=destin;
        while(x!=sursa){
            f[from[x]][x]++;
            f[x][from[x]]--;
            x=from[x];
        }
    }
    return ans;
}

int main(){
    FILE *fin, *fout;
    fin=fopen("adapost.in", "r");
    fout=fopen("adapost.out", "w");
    fscanf(fin, "%d", &n);
    for(int i=1; i<=n; i++) fscanf(fin, "%lf%lf", &a[i], &b[i]);
    for(int i=1; i<=n; i++) fscanf(fin, "%lf%lf", &x[i], &y[i]);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) km[i][j]=sqrt((a[i]-x[j])*(a[i]-x[j])+(b[i]-y[j])*(b[i]-y[j]));
    double rez=0, pas=750;
    for(int i=0; i<30; i++){
        if(!check(rez+pas)) rez+=pas;
        pas*=0.5;
    }
    rez+=pas;
    graf(rez);
    fprintf(fout, "%.12lf %.12lf\n", rez, fmcm());
    fclose(fin);
    fclose(fout);
    return 0;
}