Cod sursa(job #2085502)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 10 decembrie 2017 12:09:52
Problema Adapost Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
FILE *f = fopen("adapost.in","r");
FILE *g = fopen("adapost.out","w");
pair<double,double> S[405];
pair<double,double> A[405];
int T[805];
priority_queue< pair<double,int>,vector< pair<double,int> >,greater< pair<double,int> > > H;
vector<int> G[805];
double Cst[805][805];
int C[805][805];
int F[805][805];
double dist[805];
double oldd[805];
double reald[805];
bool U[805];
int L[805];
int R[805];
int N;
int FF;
double Fst;
int s = 0,d = 804,len;
bool dijkstra(int S,int D){
    for(int i = s;i <= d;i++){
        dist[i] = 1e8;
        T[i] = 0;
    }
    dist[S] = 0;
    H.push({0,S});
    while(!H.empty()){
        int nod = H.top().second;
        double cst = H.top().first;
        H.pop();
        if(cst != dist[nod]){
            continue;
        }
        for(auto it:G[nod]){
            if(F[nod][it] < C[nod][it]){
                double newd = dist[nod] + oldd[nod] + Cst[nod][it] - oldd[it];
                if(newd < dist[it]){
                    dist[it] = newd;
                    T[it] = nod;
                    reald[it] = Cst[nod][it] + reald[nod];
                    H.push({dist[it],it});
                }
            }
        }
    }
    if(dist[D] == 1e8){
        return 0;
    }
    memcpy(oldd,reald,sizeof(reald));
    int fmin = 1 << 30;
    for(int nod = D;nod != S;nod = T[nod]){
        fmin = min(fmin,C[T[nod]][nod] - F[T[nod]][nod]);
    }
    FF += fmin;
    Fst += reald[D] * fmin;
    for(int nod = D;nod != S;nod = T[nod]){
        F[T[nod]][nod] += fmin;
        F[nod][T[nod]] -= fmin;
    }
    return 1;
}
bool pairup(int nod){
    if(U[nod]){
        return 0;
    }
    U[nod] = 1;
    for(auto it:G[nod]){
        if(R[it] == 0 || pairup(R[it])){
            L[nod] = it;
            R[it] = nod;
            return 1;
        }
    }
    return 0;
}
int cuplaj(){
    memset(L,0,sizeof(L));
    memset(R,0,sizeof(R));
   int c = 0;
   bool ok = 1;
   while(ok){
        ok = 0;
        memset(U,0,sizeof(U));
        for(int i = 1;i <= N;i++){
            if(L[i] == 0 && pairup(i)){
                c++;
                ok = 1;
            }
        }
   }
   return c;
}
void addedge(int a,int b,int c,double d)
{
    G[a].push_back(b);
    G[b].push_back(a);
    C[a][b] = c;
    Cst[a][b] = d;
    Cst[b][a] = -d;
}
bool ok(double val,bool withSD){
    for(int i = s;i <= d;i++){
        G[i].clear();
    }
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= N;j++){
            double dist = sqrt( (S[i].first - A[j].first) * (S[i].first - A[j].first) + (S[i].second - A[j].second) * (S[i].second - A[j].second) );
            if(val - dist > 1e-6){
                if(withSD){
                    addedge(s,i,1,0);
                    addedge(j + N,d,1,0);
                    addedge(i,j + N,1,dist);
                }
                else {
                    G[i].push_back(j + N);
                    G[j + N].push_back(i);
                }
            }
        }
    }
    if(!withSD){
        return cuplaj() == N;
    }
    return 1;
}
int main()
{
    fscanf(f,"%d",&N);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%lf %lf",&S[i].first,&S[i].second);
    }
    for(int i = 1;i <= N;i++){
        fscanf(f,"%lf %lf",&A[i].first,&A[i].second);
    }
    double st = 0,dr = 2000;
    while(dr - st > 1e-6){
        double mid = (st + dr) / 2;
        if(ok(mid,0)){
            dr = mid;
        }
        else {
            st = mid;
        }
    }
    fprintf(g,"%.6f ",dr);
    ok(dr,1);
    while(dijkstra(s,d));
    fprintf(g,"%.6f",Fst);
    fclose(f);
    fclose(g);
    return 0;
}