Cod sursa(job #403040)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 24 februarie 2010 15:33:36
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.71 kb
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<queue>
#define Nmx 505
#define INF 1000001
#define Mmx 850
#define pb push_back
#define mp make_pair

using namespace std;


struct coord{ double x,y;};
int n,nr,N,viz[Nmx];
int r[Nmx],l[Nmx];
coord a[Nmx],b[Nmx];
vector<int> g[Nmx*2];
struct date{
    int x1,x2;
    double d;
}c[Nmx*Nmx];

vector<pair < int,double > > G1[Mmx];
int F[Mmx][Mmx],C[Mmx][Mmx],prec[Mmx],viz1[Mmx],Q[Mmx*Mmx*10];
double cost[Mmx],solutzie;

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);
    N=2*n+1;
    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;
    }
    solutzie=c[st].d;
    printf("%lf ",c[st].d);
}

int belmand()
{
    vector<pair <int,double> >:: iterator it;
    int st,dr,nod;
    for(int i=1;i<=N;++i)
    {
        cost[i]=INF;
        prec[i]=0;
        viz[i]=0;
    }
    cost[0]=0;
    Q[st=dr=1]=0;
    viz1[0]=1;
    while(st<=dr)
    {
        nod=Q[st];
        viz1[nod]=0;
        for(it=G1[nod].begin();it!=G1[nod].end();++it)
            if(C[nod][it->first]-F[nod][it->first]>0&&cost[it->first]>cost[nod]+it->second)
            {
                cost[it->first]=cost[nod]+it->second;
                prec[it->first]=nod;
                if(!viz1[it->first])
                {
                    Q[++dr]=it->first;
                    viz1[it->first]=1;
                }
            }
        ++st;
    }
    if(cost[N]<INF)
        return 1;
    return 0;
}

struct comp
{
	bool operator()(int i,int j)
	{
		return cost[i]>cost[j];
	}
};
priority_queue<int,vector<int>,comp> q;



int dijkstra()
{
    vector<pair <int,double> >:: iterator it;
	int i,nod;
	for(i=1;i<=N;i++)
		cost[i]=INF;
	q.push(0);
	cost[0]=0;
	while(!q.empty())
	{
		nod=q.top();
		viz1[nod]=0;
		q.pop();
		for(it=G1[nod].begin();it!=G1[nod].end();++it)
			if(C[nod][it->first]-F[nod][it->first]>0&&cost[it->first]>cost[nod]+it->second)
			{
				cost[it->first]=cost[nod]+it->second;
                prec[it->first]=nod;
				if(viz1[it->first]!=1)
					q.push(it->first),viz1[it->first]=1;
			}
	}
	if(cost[N]<INF)
        return 1;
    return 0;
}


void flux()
{
    int x,y;
    for(int i=1;i<=nr&&c[i].d<=solutzie;++i)
    {
        x=c[i].x1;y=c[i].x2+n;
        C[x][y]=C[0][x]=C[y][N]=1;
        G1[x].pb(mp(y,c[i].d));
        G1[y].pb(mp(x,-c[i].d));
        G1[x].pb(mp(0,0));
        G1[0].pb(mp(x,0));
        G1[y].pb(mp(N,0));
        G1[N].pb(mp(y,0));
    }
    double sol=0;
    int i,cp=0;
    while(dijkstra())
    {
        int Vmin=INF;
        for(i=N;i!=0;i=prec[i])
            Vmin=min(Vmin,C[prec[i]][i]-F[prec[i]][i]);
        for(i=N;i!=0;i=prec[i])
        {
            F[prec[i]][i]+=Vmin;
            F[i][prec[i]]-=Vmin;
        }
        if(Vmin)
        {
            sol+=cost[N];
            cp++;
        }
    }
    printf("%lf\n",sol);
}

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