Cod sursa(job #2333870)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 2 februarie 2019 00:55:46
Problema Adapost Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.35 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("adapost.in");
ofstream g("adapost.out");

int n,m,S,D,i,j,x,y,c,z,tata[810],cap[810][810];
double flxmax,d[810],real_d[810],dist[810],cost[810][810];
vector<int> v[810];
//////////////////////////////////////////
int ST[410],DR[410],pleis[410][410];
vector<pair<double,pair<int,int> > > u;
bitset<410> viz;
struct neim{
    double x,y;
};
neim sold[410],adap[410];
//////////////////////////////////////////
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(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(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(i=1;i<=n;i++)
            if(!ST[i])
                if(tri(i))
                    ret++,ok=1;
    }
    for(i=1;i<=n;i++)
        v[i].resize(0);
    return (ret==n);
}
//////////////////////////////////////////

int main()
{
    f>>n;
    for(i=1;i<=n;i++)f>>sold[i].x>>sold[i].y;
    for(i=1;i<=n;i++)f>>adap[i].x>>adap[i].y;
    for(i=1;i<=n;i++)
        for(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());
    for(i=0;i<u.size();i++)
        pleis[u[i].second.first][u[i].second.second]=i+1;
    int lo=1,hi=u.size();
    while(lo<hi)
    {
        int mi=(lo+hi)/2;
        if(okcup(mi))
            hi=mi;
        else
            lo=mi+1;
    }
    g<<fixed<<setprecision(10)<<u[lo-1].first<<' ';

    S=1,D=2*n+2;
    for(i=2;i<=n+1;i++)
    {
        v[1].push_back(i);
        v[i].push_back(1);
        cap[1][i]=1;
    }
    for(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(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(););
    g<<fixed<<setprecision(10)<<flxmax;
//    f>>n>>m>>S>>D;
//    for(i=1;i<=m;i++)
//    {
//        f>>x>>y>>c>>z;
//        v[x].push_back(y);
//        v[y].push_back(x);
//        cap[x][y]=c;
//        cost[x][y]=z;
//        cost[y][x]=-z;
//    }
//    bellman();
//    for(;djikstra(););
//    g<<flxmax;
    return 0;
}