Pagini recente » Cod sursa (job #245172) | Cod sursa (job #2808326) | Cod sursa (job #2651699) | Cod sursa (job #2614667) | Cod sursa (job #469509)
Cod sursa(job #469509)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>
#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];
struct cmp
{
bool operator()(const double &a, const double &b)const
{
return a<b;
}
};
int n,i,j,f[805][805],cap[805][805],a,b,mid,tt[805],cuplaj,mindif[805],first,aux,minim,st[405],dr[405];
double val[160005],cost[805][805],sol,dist[805];
bool k;
class heap_cmp
{
public:
inline bool operator()(const int &x,const int &y)
{
return dist[x]>dist[y];
}
};
priority_queue<int,vector<int>,heap_cmp> heap;
bitset<805> viz;
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 pairup(int node)
{
int i;
if (viz.test(node))
return 0;
viz.flip(node);
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;
viz&=0;
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)
dist[i]=inf;
viz&=0;
viz.flip(sursa);
heap.push(sursa);
mindif[sursa]=inf;
dist[sursa]=0;
while (!heap.empty())
{
first=heap.top();
heap.pop();
viz[first]=0;
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.test(*u))
{
heap.push(*u);
viz.flip(*u);
}
}
}
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;
}