Pagini recente » Cod sursa (job #1445207) | Cod sursa (job #3226805) | Cod sursa (job #2870782) | Cod sursa (job #401500) | Cod sursa (job #469463)
Cod sursa(job #469463)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <cstring>
#define sursa (2*n+1)
#define dest (2*n+2)
#define inf 0x7fffffff
using namespace std;
vector<int> graf[805];
vector<int>::iterator u;
struct per
{
double x,y;
} v[405],ad[405];
int n,i,j,f[805][805],cap[805][805],a,b,mid,viz[805],tt[805],cuplaj,heap[805],mindif[805],x,first,aux,minim,st[405],dr[405];
double val[160005],cost[805][805],sol,dist[805];
bool k;
inline double plandist(per punct1,per punct2)
{
return sqrt((punct1.x-punct2.x)*(punct1.x-punct2.x)+(punct1.y-punct2.y)*(punct1.y-punct2.y));
}
int cmp(const double &a,const double &b)
{
return a<b;
}
inline void heap_up(int p)
{
while (p>1 && dist[heap[p]]<dist[heap[p>>1]])
{
aux=heap[p];
heap[p]=heap[p>>1];
heap[p>>1]=aux;
viz[heap[p]]=p;
viz[heap[p>>1]]=p>>1;
p>>=1;
}
}
inline void heap_down(int p)
{
while ((p*2<=x && dist[heap[p]]>dist[heap[p*2]]) || (p*2+1<=x && dist[heap[p]]>dist[heap[p*2+1]]))
{
if (p*2+1<=x)
if (dist[heap[p*2]]<dist[heap[p*2+1]])
minim=p*2;
else
minim=p*2+1;
else
minim=p*2;
aux=heap[p];
heap[p]=heap[minim];
heap[minim]=aux;
viz[heap[p]]=p;
viz[heap[minim]]=minim;
p=minim;
}
}
int pairup(int node)
{
int i;
if (viz[node])
return 0;
viz[node]=1;
for (i=1;i<=n;++i)
if (!dr[i] && cost[node][i+n]<=val[mid])
{
dr[i]=node;
st[node]=i;
return 1;
}
for (i=1;i<=n;++i)
if (cost[node][i+n]<=val[mid])
if (pairup(dr[i]))
{
dr[i]=node;
st[node]=i;
return 1;
}
return 0;
}
int main()
{
freopen("adapost.in","r",stdin);
freopen("adapost.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
scanf("%lf %lf",&v[i].x,&v[i].y);
for (i=1;i<=n;++i)
{
scanf("%lf %lf",&ad[i].x,&ad[i].y);
for (j=1;j<=n;++j)
{
val[(i-1)*n+j]=plandist(ad[i],v[j]);
graf[j].push_back(i+n);
graf[i+n].push_back(j);
cost[j][i+n]=val[(i-1)*n+j];
cap[j][i+n]=1;
cost[i+n][j]=-cost[j][i+n];
}
graf[sursa].push_back(i);
graf[i].push_back(sursa);
cap[sursa][i]=1;
graf[i+n].push_back(dest);
graf[dest].push_back(i+n);
cap[i+n][dest]=1;
}
sort(val+1,val+n*n+1,cmp);
a=1;
b=n*n;
while (a<=b)
{
mid=a+((b-a)>>1);
memset(st,0,sizeof(st));
memset(dr,0,sizeof(dr));
do
{
k=true;
memset(viz,0,sizeof(viz));
for (i=1;i<=n;++i)
if (!st[i] && pairup(i))
k=false;
}
while (!k);
cuplaj=0;
for (i=1;i<=n;++i)
if (st[i])
++cuplaj;
if (cuplaj==n)
b=mid-1;
else
a=mid+1;
}
//flux maxim de cost minim
/*k=true;
while (k)
{
k=false;
for (i=1;i<=dest;++i)
{
viz[i]=0;
dist[i]=inf;
}
heap[1]=sursa;
viz[sursa]=1;
heap[1]=sursa;
mindif[sursa]=inf;
dist[sursa]=0;
x=1;
while (x)
{
first=heap[1];
viz[first]=0;
if (x==1)
x=0;
else
{
heap[1]=heap[x--];
viz[heap[1]]=1;
heap_down(1);
}
if (first==dest)
k=true;
for (u=graf[first].begin();u!=graf[first].end();++u)
if (cap[first][*u]>f[first][*u] && dist[first]+cost[first][*u]<dist[*u] && cost[first][*u]<=val[b+1] && cost[*u][first]<=val[b+1])
{
dist[*u]=dist[first]+cost[first][*u];
if (cap[first][*u]-f[first][*u]<mindif[first])
mindif[*u]=cap[first][*u]-f[first][*u];
else
mindif[*u]=mindif[first];
tt[*u]=first;
if (viz[*u])
heap_up(viz[*u]);
else
{
heap[++x]=*u;
viz[*u]=x;
heap_up(x);
}
}
}
if (k)
for (i=dest;i!=sursa;i=tt[i])
{
sol+=cost[tt[i]][i]*mindif[dest];
f[tt[i]][i]+=mindif[dest];
f[i][tt[i]]-=mindif[dest];
}
}*/
printf("%.5lf %.5lf",val[b+1],sol);
return 0;
}