Cod sursa(job #1789258)

Utilizator Bodo171Bogdan Pop Bodo171 Data 26 octombrie 2016 20:23:16
Problema Adapost Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <iostream>
#include<fstream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
const int nmax=805;
int fl[nmax][nmax],c[nmax][nmax],v[nmax][nmax];
int G[nmax],q[nmax],prec[nmax];
double d[nmax][nmax],cost[nmax],dist[nmax*nmax],x1[nmax],y11[nmax],x2[nmax],y2[nmax],costul;
const double eps=0.0000001;
int i,n,m,j,sink,source,node,start,u,p,flow,k;
bool inq[nmax];
bool ok;
bool bfs()
{
    for(i=1;i<=sink;i++)
        prec[i]=0;
    u=1;q[u]=source;
    prec[source]=-1;p=1;
    while(p<=u)
    {
        start=q[p];p++;
        for(i=1;i<=G[start];i++)
        {
            node=v[start][i];
            if(prec[node]==0&&fl[start][node]<c[start][node])
            {
                u++;
                prec[node]=start;
                q[u]=node;
                if(node==sink) return 1;
            }
        }
    }
    return 0;
}
bool bf()
{
    for(i=1;i<=sink;i++)
        prec[i]=0,cost[i]=(1<<30),inq[i]=0;
    queue<int> qbf;
    qbf.push(source);
    prec[source]=-1;cost[source]=0;
    while(!qbf.empty())
    {
        start=qbf.front();qbf.pop();
        inq[start]=0;
        for(i=1;i<=G[start];i++)
        {
            node=v[start][i];
            if(cost[node]-(cost[start]+d[start][node])>eps&&fl[start][node]<c[start][node])
            {
                if(!inq[node]) {qbf.push(node);inq[node]=1;}
                cost[node]=cost[start]+d[start][node];
                prec[node]=start;
            }
        }
    }
    return (cost[sink]!=(1<<30));
}
bool check(int x)
{
    for(i=1;i<=n;i++)
    {
        G[i]=1;G[n+i]=1;
        fl[source][i]=0;fl[i][source]=0;
        fl[n+i][sink]=0;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fl[i][n+j]=0;fl[n+j][i]=0;
            if(d[i][n+j]<=dist[x])
            {
                G[i]++;G[n+j]++;
                v[i][G[i]]=n+j;
                v[n+j][G[n+j]]=i;
            }
        }
    flow=0;
    while(bfs())
    {
        node=sink;
        while(node!=source)
        {
            fl[prec[node]][node]++;
            fl[node][prec[node]]--;
            node=prec[node];
        }
        flow++;
    }
    return (flow==n);
}
int main()
{
    ifstream f("adapost.in");
    ofstream g("adapost.out");
    f>>n;source=2*n+1;sink=2*n+2;
    for(i=1;i<=n;i++)
    {
        f>>x1[i]>>y11[i];
    }
    for(i=1;i<=n;i++)
    {
        f>>x2[i]>>y2[i];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
    {
        d[i][n+j]=sqrt((x1[i]-x2[j])*(x1[i]-x2[j])+(y11[i]-y2[j])*(y11[i]-y2[j]));
        d[n+j][i]=d[i][n+j]*(-1);
        c[i][n+j]=1;
        k++;
        dist[k]=d[i][n+j];
    }
    for(i=1;i<=n;i++)
    {
        G[source]++;
        v[source][G[source]]=i;
        c[source][i]=1;
        G[i]++;
        v[i][G[i]]=source;
        G[n+i]++;
        v[n+i][G[n+i]]=sink;
        c[n+i][sink]=1;
    }
    sort(dist+1,dist+k+1);
    int pr=1,ul=k;
    while(ul-pr>1)
    {
        m=(pr+ul)/2;
        if(check(m)) ul=m;
        else pr=m;
    }
    ok=check(ul);
    for(i=1;i<=sink;i++)
        for(j=1;j<=sink;j++)
         fl[i][j]=0;
    while(bf())
    {
        node=sink;
        while(node!=source)
        {
            fl[prec[node]][node]++;
            fl[node][prec[node]]--;
            node=prec[node];
        }
        costul+=cost[sink];
    }
    g<<fixed<<setprecision(6)<<dist[ul]<<' '<<costul;
    return 0;
}