Cod sursa(job #2387922)

Utilizator refugiatBoni Daniel Stefan refugiat Data 25 martie 2019 14:04:22
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.13 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
ifstream si("adapost.in");
ofstream so("adapost.out");
int n, m, S, D, x, y, c, z, tata[805], cap[805][805];
double flxmax,d[805],real_d[805],dist[805],cost[805][805];
vector<int> v[805];
int ST[405],DR[405],pleis[405][405];
vector<pair<double,pair<int,int> > > u;
bitset<405> viz;
struct neim{
    double x,y;
};
neim sold[405],adap[405];
void bellman() {
    memset(dist,127,sizeof(dist));
    bitset<360> in;
    in.reset();
    dist[S]=0;
    in[S]=1;
    queue<int> q;
    q.push(S);
    while(q.size()) {
        int x=q.front();
        q.pop();
        in[x]=0;
        for(auto it:v[x])
            if(cap[x][it])
                if(dist[it]>dist[x]+cost[x][it])
                {
                    dist[it]=dist[x]+cost[x][it];
                    if(!in[it])
                        q.push(it);
                    in[it]=1;
                }
    }
}
bool djikstra()
{
    memset(d,127,sizeof(d));
    memset(real_d,127,sizeof(real_d));
    memset(tata,0,sizeof(tata));
    priority_queue<pair<int,int> > q;
    d[S]=real_d[S]=0;
    q.push({0,S});
    while(q.size()) {
        int y=-q.top().first, x=q.top().second;
        q.pop();
        if(y>d[x]) continue;
        for(auto it:v[x])
            if(cap[x][it])
                if(d[it]>d[x]+cost[x][it]+dist[x]-dist[it]) {
                    d[it]=d[x]+cost[x][it]+dist[x]-dist[it];
                    real_d[it]=real_d[x]+cost[x][it];
                    q.push({-d[it],it});tata[it]=x;
                }
    }
    for(int i=1; i<=n; i++)
        dist[i]=real_d[i];
    if(dist[D]>1e9)
        return 0;
    int ke=1e9;
    for(int x=D; tata[x]; x=tata[x])
        ke=min(ke,cap[tata[x]][x]);
    for(int x=D; tata[x]; x=tata[x]) {
        cap[tata[x]][x]-=ke;
        cap[x][tata[x]]+=ke;
    }
    flxmax+=ke*dist[D];
    return 1;
}

bool tri(int poz) {
    if(viz[poz])
        return 0;
    viz[poz]=1;
    for(auto it:v[poz])
        if(!DR[it]) {
            ST[poz]=it;
            DR[it]=poz;
            return 1;
        }
    for(auto it:v[poz])
        if(tri(DR[it])) {
            ST[poz]=it;
            DR[it]=poz;
            return 1;
        }
    return 0;
}
bool okcup(int mi) {
    int ret=0;
    for(int i=0; i<mi; i++)
        v[u[i].second.first].push_back(u[i].second.second);
    memset(ST,0,sizeof(ST));
    memset(DR,0,sizeof(DR));
    bool ok=1;
    while(ok) {
        ok=0;
        viz.reset();
        for(int i=1; i<=n; i++)
            if(!ST[i])
                if(tri(i)) {
                    ret++;
                    ok=1;
                }
    }
    for(int i=1; i<=n; i++)
        v[i].resize(0);
    return (ret==n);
}

int main() {
    si>>n;
    for(int i=1; i<=n; i++)
        si>>sold[i].x>>sold[i].y;
    for(int i=1; i<=n; i++)
        si>>adap[i].x>>adap[i].y;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            u.push_back({sqrt((sold[i].x-adap[j].x)*(sold[i].x-adap[j].x)
                        +(sold[i].y-adap[j].y)*(sold[i].y-adap[j].y)),{i,j}});
    sort(u.begin(), u.end());
    int lo=1, hi=u.size();
    while(lo<hi) {
        int mi=(lo+hi)/2;
        if(okcup(mi))
            hi=mi;
        else
            lo=mi+1;
    }
    so<<fixed<<setprecision(10)<<u[lo-1].first<<' ';

    S=1;
    D=2*n+2;
    for(int i=2; i<=n+1; i++)
    {
        v[1].push_back(i);
        v[i].push_back(1);
        cap[1][i]=1;
    }
    for(int i=n+2; i<=2*n+1; i++)
    {
        v[i].push_back(2*n+2);
        v[2*n+2].push_back(i);
        cap[i][2*n+2]=1;
    }
    for(int i=0; i<lo; i++)
    {
        int x=u[i].second.first+1, y=u[i].second.second+n+1;
        double z=u[i].first;
        v[x].push_back(y);
        v[y].push_back(x);
        cap[x][y]=1;
        cost[x][y]=z;
        cost[y][x]=-z;
    }
    n=2*n+2;
    bellman();
    for(;djikstra(););
    so<<fixed<<setprecision(10)<<flxmax;
    return 0;
}