Cod sursa(job #2085528)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 10 decembrie 2017 12:32:23
Problema Adapost Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 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];
queue<int> Q;
vector<int> G[805];
double Cst[805][805];
int C[805][805];
int F[805][805];
double dd[405][405];
double dist[805];
double DD[400 * 400 + 5];
bool U[805];
int L[805];
int R[805];
int N;
int FF;
double Fst;
int s = 0,d = 804,len;
bool bellmand(int S,int D){
    for(int i = s;i <= d;i++){
        dist[i] = 1e8;
        T[i] = 0;
    }
    dist[S] = 0;
    inQ[S] = 1;
    Q.push(S);
    while(!Q.empty()){
        int nod = Q.front();
        inQ[nod] = 0;
        Q.pop();
        for(auto it:G[nod]){
            if(C[nod][it] > F[nod][it] && dist[it] > dist[nod] + Cst[nod][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;
    }
    int fmin = 1;
    FF += fmin;
    Fst += dist[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 = 1;i <= N;i++){
        G[i].clear();
    }
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= N;j++){
            if(val >= dd[i][j]){
                if(withSD){
                    addedge(s,i,1,0);
                    addedge(j + N,d,1,0);
                    addedge(i,j + N,1,dd[i][j]);
                }
                else {
                    G[i].push_back(j);
                }
            }
        }
    }
    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);
    }
    int len = 0;
    for(int i = 1;i <= N;i++){
        for(int j = 1;j <= N;j++){
            dd[i][j] = 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] = dd[i][j];
        }
    }
    sort(DD + 1,DD + 1 + len);
    int st = 0,dr = len;
    while(dr - st > 1){
        int mid = (st + dr) / 2;
        if(ok(DD[mid],0)){
            dr = mid;
        }
        else {
            st = mid;
        }
    }
    fprintf(g,"%.6f ",DD[dr]);
    ok(DD[dr],1);
    while(bellmand(s,d));
    fprintf(g,"%.6f",Fst);
    fclose(f);
    fclose(g);
    return 0;
}