Cod sursa(job #402339)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 23 februarie 2010 19:56:44
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#define Nmx 405
#define INF 1000001

using namespace std;

struct coord{ double x,y;};
int n,nr,Q[Nmx*Nmx*10],st,dr,viz[Nmx*2],prec[Nmx*2];
int C[Nmx*2][Nmx*2],F[Nmx*2][Nmx*2],r[Nmx*2],l[Nmx*2],;
coord a[Nmx],b[Nmx];
vector<int> g[Nmx];

struct date{
    int x1,x2;
    double d;
}c[Nmx];

double dist(double x,double y,double x1,double y1)
{
    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}

bool cmp(const date &a,const date &b)
{
    return a.d<b.d;
}

void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&b[i].x,&b[i].y);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            c[++nr].d=dist(a[i].x,a[i].y,b[j].x,b[j].y);
            c[nr].x1=i;c[nr].x2=j;
        }
    sort(c+1,c+nr+1,cmp);
}

int pairup (int nod)
{
    int i;
    if (viz[nod])
        return 0;
    viz[nod]=1;
    for (i=0; i<(int)g[nod].size (); ++i)
        if (!r[g[nod][i]])
        {
            r[g[nod][i]]=nod;
            l[nod]=g[nod][i];
            return 1;
        }
    for (i=0; i<(int)g[nod].size (); ++i)
        if (pairup (r[g[nod][i]]))
        {
            l[nod]=g[nod][i];
            r[g[nod][i]]=nod;
            return 1;
        }
    return 0;
}

void build_graph(double x)
{
    for(int i=1;i<=n;++i)
    {
        g[i].clear();
        l[i]=0;
        r[i]=0;
    }
    for(int i=1;i<=nr&&c[i].d<=x;++i)
        g[c[i].x1].push_back(c[i].x2);

}


int este(double x)
{
    build_graph(x);
    int i,ok,cupl=0;
    do
    {
        ok=0;
        memset(viz,0,sizeof (viz));
        for (i=1; i<=n; ++i)
            if (!l[i] && pairup (i))
            {
                ++cupl;
                ok=1;
            }
    }
    while (ok);
    if(cupl!=n)
        return 0;
    return 1;
}

void solve()
{
    int st=1,dr=nr;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(este(c[mij].d))
            dr=mij-1;
        else st=mij+1;
    }
    printf("%lf ",c[st].d);
}

int main()
{
    freopen("adapost.in","r",stdin);
    freopen("adapost.out","w",stdout);
    citire();
    solve();
    return 0;
}