Cod sursa(job #1528920)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 20 noiembrie 2015 11:08:23
Problema Adapost Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <fstream>
#include <cstring>
#include <queue>
#define inf 1<<30
#define nmax 810
#define eps 0.0001
using namespace std;
struct point{double x;double y;};
point p[nmax];

double r[nmax][nmax],sol;
short c[nmax][nmax],f[nmax][nmax];
int n,st[nmax],dr[nmax];
int dest;
bitset <nmax*2> uz;
vector <int> v[nmax];
queue <int> q;


double dist(const point &a,const point &b)
{
    return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cuplaj(int x)
{
    int i,y;
    uz[x]=1;
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (dr[y]==0) {
            st[x]=y;
            dr[y]=x;
            return 1;
        }
    }
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (uz[dr[y]]=0&&cuplaj(dr[y])) {
            st[x]=y;
            dr[y]=x;
            return 1;
        }
    }
    return 0;
}
int solvesol()
{
    int i,ok;
    for (i=1;i<=n;i++)
        st[i]=0,dr[i]=0;
    do
    {
        ok=0;
        uz.reset();
        for (i=1;i<=n;i++)
            if (st[i]==0&&cuplaj(i))
                ok=1;

    }while (ok);
    for (i=1;i<=n;i++)
        if (st[i]==0)
            return 0;
    return 1;
}

double d[nmax];
int t[nmax];

void make_graph(double mid,int l)
{
    int i,j;
    for (i=1;i<=n;i++)
        v[i].clear();
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++)
            if (r[i][j]<=mid) {
                v[i].push_back(l==0?j-n:j);
                if (l==1) {
                    v[j].push_back(i);
                    c[i][j]=1;
                }
            }
    if (l==1) {
        for (i=1;i<=n;i++) {
            v[0].push_back(i);
            v[i].push_back(0);
            c[0][i]=1;
        }
        for (i=n+1;i<=2*n;i++) {
            v[i].push_back(dest);
            v[dest].push_back(i);
            c[i][dest]=1;
        }
    }
}
double bfs()
{
    int x,y,i;
    for (i=1;i<=dest;i++)
        d[i]=inf;
    q.push(0);
    uz.reset();
    uz[0]=1;
    while (!q.empty()) {
        x=q.front();
        q.pop();
        uz[x]=0;
        for (i=0;i<v[x].size();i++) {
            y=v[x][i];
            if (f[x][y]<c[x][y]&&d[y]>d[x]+r[x][y]) {
                d[y]=d[x]+r[x][y];
                t[y]=x;
                if (uz[y]==0) {
                    d[y]=d[x]+r[x][y];
                    if (uz[y]==0) {
                        uz[y]=1;
                        q.push(y);
                    }
                }
            }
        }
    }
    if (d[dest]==inf)
        return 0;
    int add=inf;
    for (i=dest;i;i=t[i])
        add=min(add,c[t[i]][i]-f[t[i]][i]);
    return add*d[dest];


}
double fmcm()
{
    double a=0,b=0;
    int i;

    while (1) {
        a=bfs();
        if (a==0)
            break;
        b+=a;
        for (i=dest;i;i=t[i]) {
            f[t[i]][i]++;
            f[i][t[i]]--;
        }
    }
    return b;
}



int main()
{
    ifstream fin("adapost.in");
    ofstream fout("adapost.out");
    fin>>n;
    int i,j;
    double kx,ky;
    for (i=1;i<=2*n;i++) {
        fin>>kx>>ky;
        p[i].x=kx;p[i].y=ky;
    }
    dest=2*n+1;
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++) {
            r[i][j]=dist(p[i],p[j]);
            r[j][i]=-r[i][j];
        }

    double st=0,dr=1<<30,mid;

    while (st<=dr) {
        mid=(st+dr)/2.0;
        make_graph(mid,0);
        if (solvesol()) {
            sol=mid;
            dr=mid-eps;
        }
        else
            st=mid+eps;
    }
    make_graph(sol,1);

    fout<<setprecision(10)<<fixed<<sol/1.0<<' '<<fmcm()/1.0<<'\n';

    return 0;
}