Pagini recente » Cod sursa (job #2335251) | Cod sursa (job #3318670) | Cod sursa (job #1732634) | Cod sursa (job #1610407) | Cod sursa (job #402636)
Cod sursa(job #402636)
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define file_in "adapost.in"
#define file_out "adapost.out"
#define Nmax 500
#define Inf 0x3f3f3f3f
vector<int> G[Nmax*Nmax];
int viz[Nmax*Nmax];
int cuplaj1[Nmax*20];
int cuplaj2[Nmax*20];
struct ad
{
int x,y;
double c;
}
v[Nmax*Nmax];
int nr,n;
double a1[Nmax],b2[Nmax];
double a2[Nmax],b1[Nmax];
double C[Nmax][Nmax];
double P[Nmax][Nmax];
double F[Nmax][Nmax];
int S,D;
double dm[Nmax*Nmax];
int t[Nmax];
inline double dist(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int cmp(ad a, ad b)
{
return (a.c<b.c);
}
int cuplaj(int nod)
{
int x;
if (viz[nod]==1)
return 0;
viz[nod]=1;
for (int i=0;i<G[nod].size();++i)
{
x=G[nod][i];
if (cuplaj1[x]==0)
{
cuplaj2[nod]=1;
cuplaj1[x]=nod;
return 1;
}
}
for (int i=0;i<G[nod].size();++i)
{
x=G[nod][i];
if (cuplaj1[x]!=nod && cuplaj(cuplaj1[x]))
{
cuplaj2[nod]=1;
cuplaj1[x]=nod;
return 1;
}
}
return 0;
}
int good(double nod)
{
int i,ok,nrr;
for (i=1;i<=nr;++i)
G[i].clear();
memset(cuplaj1,0,sizeof(cuplaj1));
memset(cuplaj2,0,sizeof(cuplaj2));
//contruieste noul graf
for (i=1;i<=nr && v[i].c<=nod;++i)
G[v[i].x].push_back(v[i].y);
nrr=0;
///baga cuplaj
ok=1;
while(ok)
{
ok=0;
memset(viz,0,sizeof(viz));
for (i=1;i<=n;++i)
if (cuplaj2[i]==0 && cuplaj(i))
{
nrr++;
ok=1;
}
}
return (n==nrr);
}
inline int bf()
{
for (int i=1;i<=n;++i)
dm[i]=Inf,
viz[i]=0;
int q[Nmax*Nmax];
int st=0,dr=1, nod;
q[1]=S;
dm[S]=0;
viz[S]=1;
while (st<dr)
{
nod=q[++st];
for (int i=1;i<=n;++i)
if ((dm[nod]+P[nod][i]<dm[i]) && (C[nod][i]-F[nod][i]>0))
{
dm[i]=dm[nod]+P[nod][i];
t[i]=nod;
if (!viz[i])
{
q[++dr]=i;
viz[i]=1;
}
}
viz[nod]=0;
}
return (dm[D]<Inf/2);
}
void solve()
{
double sol=0;
while (bf())
{
int r=C[t[D]][D]-F[t[D]][D];
for (int i=D;i!=S;i=t[i])
if (C[t[i]][i]-F[t[i]][i]<r)
r=C[t[i]][i]-F[t[i]][i];
for (int i=D;i!=S;i=t[i])
F[t[i]][i]+=r,
F[i][t[i]]-=r;
sol+=r*dm[D];
}
printf(".5lf", sol);
}
int main()
{
int i,ls,ld,sol,mij,j;
double d;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &n);
for (i=1;i<=n;++i)
scanf("%lf %lf", &a1[i], &b1[i]);
for (i=1;i<=n;++i)
scanf("%lf %lf", &a2[i], &b2[i]);
//formez distantele
nr=0;
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
{
d=dist(a1[i],b1[i],a2[j],b2[j]);
v[++nr].c=d;
v[nr].x=i;
v[nr].y=j;
C[i][j]=1;
P[i][j]=d;
P[j][i]=-d;
}
//sorteaza in functie de distanta
sort(v+1,v+nr+1,cmp);
/*for (i=1;i<=nr;++i)
printf("%.5lf\n", v[i].c); */
//cautare binara intervalu [1,nr]
ls=1;
ld=nr;
while(ls<=ld)
{
mij=(ls+ld)>>1;
if (good(v[mij].c))
{
sol=mij;
ld=mij-1;
}
else
{
ls=mij+1;
}
}
printf("%.5lf ", v[sol].c);
S=1;//sursa
D=n;//destinatia
//al doua cerinta
//flux maxim de cost minim
solve();
fclose(stdin);
fclose(stdout);
return 0;
}