Cod sursa(job #1903222)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 5 martie 2017 01:14:05
Problema Adapost Scor 21
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>
#define pid pair<double,double>
#define x first
#define y second
#define Nmax 405
#define inf 10000000
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
double cost[2*Nmax][2*Nmax],distmin[2*Nmax],costcuplaj;
pid sold[Nmax],adap[Nmax];
int n,C[2*Nmax][2*Nmax],source,sink,tata[2*Nmax],cuplaj;
queue<int>Q;
vector<int>H[2*Nmax];
vector<int>::iterator it;
bitset<2*Nmax>viz;
double seg[Nmax*Nmax];
double distanta(int i,int j)
{
    return 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));
}
bool bellmanford()
{
    viz.reset();
    for(int i=1;i<=2*n+1;i++) distmin[i]=inf;
    distmin[source]=0;
    viz[source]=1;
    Q.push(source);
    while(Q.size())
    {
        int nod=Q.front();
        Q.pop();
        viz[nod]=0;
        if(nod==sink) continue;
        for(it=H[nod].begin();it!=H[nod].end();it++)
        {
            if(C[nod][*it] && (distmin[*it]>distmin[nod]+cost[nod][*it]))
            {
                distmin[*it]=distmin[nod]+cost[nod][*it];
                tata[*it]=nod;
                if(viz[*it]==0)
                {
                    viz[*it]=1;
                    Q.push(*it);
                }
            }
        }
    }
    if(distmin[sink]==inf) return 0;
    int fmin=inf;
    for(int i=sink;i!=source;i=tata[i])
    {
        fmin=min(fmin,C[tata[i]][i]);
    }
    for(int i=sink;i!=source;i=tata[i])
    {
        C[tata[i]][i]-=fmin;
        C[i][tata[i]]+=fmin;
    }
    cuplaj+=fmin;
    costcuplaj+=1.0*fmin*distmin[sink];
    return 1;
}
int main()
{
    int i,j,nr=0;
    double maxim=0,costminim=inf;
    fin>>n;
    sink=2*n+1;
    for(i=1;i<=n;i++) fin>>sold[i].x>>sold[i].y;
    for(i=1;i<=n;i++) fin>>adap[i].x>>adap[i].y;
    for(i=1;i<=n;i++)
    {
        for(j=n+1;j<=2*n;j++)
        {
            seg[++nr]=distanta(i,j-n);
            cost[i][j]=seg[nr];
            cost[j][i]=-seg[nr];
        }
    }
    sort(seg+1,seg+n*n+1);
    int st=1,dr=n*n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        memset(C,0,sizeof(C));
        for(i=0;i<=2*n+5;i++) H[i].clear();
        for(i=1;i<=n;i++)
        {
            C[source][i]=C[i+n][sink]=1;
            H[i].push_back(source);
            H[source].push_back(i);
            H[i+n].push_back(sink);
            H[sink].push_back(i+n);
        }
        for(i=1;i<=n;i++)
        {
            for(j=n+1;j<=2*n;j++)
            {
                if(cost[i][j]-seg[mij]< 0.000001)
                {
                    C[i][j]=1;
                    H[i].push_back(j);
                    H[j].push_back(i);
                }
            }
        }
        cuplaj=costcuplaj=0;
        while(bellmanford());
        if(cuplaj==n)
        {
            maxim=seg[mij];
            if(costcuplaj<costminim) costminim=costcuplaj;
            dr=mij-1;
        }
        else st=mij+1;
    }
    fout<<setprecision(5)<<fixed<<maxim<<" "<<costminim;
}