Cod sursa(job #2269341)

Utilizator rares9301Sarmasag Rares rares9301 Data 25 octombrie 2018 21:30:41
Problema Adapost Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.72 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];

bool inQ[805];

vector<int> G[805];

double Cst[805][805];

int C[805][805];

double dist[805];

pair<double,pair<int,int> > DD[400 * 400 + 5];

bool U[405];

int L[405];

int R[405];

int N;

double Fst;

double eps = 1e-6;

int s = 0,d = 804,len;

bool bellmand(int S,int D){

    for(int i = S;i <= D;i++){

        dist[i] = 1e8;

    }

    dist[S] = 0;

    inQ[S] = 1;

    queue<int> Q;

    Q.push(S);

    while(!Q.empty()){

        int nod = Q.front();

        inQ[nod] = 0;

        Q.pop();

        for(auto it:G[nod]){

            if(C[nod][it] > 0 && -eps > dist[nod] + Cst[nod][it] - dist[it]){

                dist[it] = dist[nod] + Cst[nod][it];

                T[it] = nod;

                if(!inQ[it]){

                    inQ[it] = 1;

                    Q.push(it);

                }

            }

        }

    }

    if(dist[D] == 1e8){

        return 0;

    }

    Fst += dist[D];

    for(int nod = D;nod != S;nod = T[nod]){

        C[T[nod]][nod] --;

        C[nod][T[nod]] ++;

    }

    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(int val,bool withSD){

    for(int i = 1;i <= N;i++){

        G[i].clear();

    }

    for(int k = 1;k <= val;k++){

        int i = DD[k].second.first;

        int j = DD[k].second.second;

        if(withSD){

            addedge(s,i,1,0);

            addedge(j + N,d,1,0);

            addedge(i,j + N,1,DD[k].first);

        }

        else {

            G[i].push_back(j);

        }

    }

    if(!withSD){

        return cuplaj() == N;

    }

    return 1;

}

int main()

{

    fscanf(f,"%d",&N);s = 0;d = 2 * N + 1;

    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);

    }

    int len = 0;

    for(int i = 1;i <= N;i++){

        for(int j = 1;j <= N;j++){

            DD[++len].first = 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) );

            DD[len].second = {i,j};

        }

    }

    sort(DD + 1,DD + 1 + len);

    int st = 0,dr = len;

    while(dr - st > 1){

        int mid = (st + dr) / 2;

        if(ok(mid,0)){

            dr = mid;

        }

        else {

            st = mid;

        }

    }

    fprintf(g,"%.6f ",DD[dr]);

    ok(dr,1);

    while(bellmand(s,d));

    fprintf(g,"%.6f",Fst);

    fclose(f);

    fclose(g);

    return 0;

}