Cod sursa(job #1903170)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 5 martie 2017 00:19:19
Problema Adapost Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cmath>
#define pid pair<double,double>
#define x first
#define y second
#define Nmax 405
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
double cost[2*Nmax][2*Nmax],distmin[2*Nmax],cuplaj,costcuplaj;
pid sold[Nmax],adap[Nmax];
int n,C[2*Nmax][2*Nmax],source,sink,tata[2*Nmax];
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]=99999999999;
    distmin[source]=0;
    viz[source]=1;
    Q.push(source);
    while(Q.size())
    {
        int nod=Q.front();
        Q.pop();
        viz[nod]=0;
        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]==99999999999) 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;
    double maxim=0,costminim=0;
    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=1;j<=n;j++)
        {
            int nr=(i-1)*n+j;
            seg[nr]=distanta(i,j);
        }
    }
    sort(seg+1,seg+n*n+1);
    int st=1,dr=n*n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        memset(cost,0,sizeof(cost));
        memset(C,0,sizeof(C));
        for(i=1;i<=n;i++)
        {
            H[i].clear();
            H[i+n].clear();
            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=1;j<=n;j++)
            {
                double dist=distanta(i,j);
                if(dist<=seg[mij])
                {
                    C[i][j+n]=1;
                    cost[i][j+n]=dist;
                    cost[j+n][i]=-dist;
                    H[i].push_back(j+n);
                    H[j+n].push_back(i);
                }
            }
        }
        cuplaj=costcuplaj=0;
        while(bellmanford());
        if(cuplaj==n)
        {
            maxim=seg[mij];
            costminim=costcuplaj;
            dr=mij-1;
        }
        else st=mij+1;
    }
    fout<<maxim<<" "<<costminim;
}