Pagini recente » Cod sursa (job #522263) | Cod sursa (job #2625039) | Cod sursa (job #3237120) | Cod sursa (job #268675) | Cod sursa (job #485781)
Cod sursa(job #485781)
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#define punct pair<double,double>
#define x first
#define y second
using namespace std;
const char iname[]="adapost.in";
const char oname[]="adapost.out";
const int maxn=805;
const double inf=1e25;
ifstream f(iname);
ofstream g(oname);
vector<int> E[maxn];
int r[maxn],l[maxn],S,D,A[maxn],been[maxn],C[maxn][maxn],F[maxn][maxn],n,i,j,p,k,step,ok;
double dis[maxn],cost[maxn][maxn],rez,m[maxn*maxn];
struct fcomp
{
bool operator()(const int &a, const int &b)
{
return dis[a]>dis[b];
}
};
priority_queue<int,vector<int>,fcomp> Q;
punct a[maxn],b[maxn];
double dist(punct a,punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int match(int x)
{
if(been[x])
return 0;
been[x]=1;
for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
if(r[*it]==-1)
{
l[x]=*it;
r[*it]=x;
return 1;
}
for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
if(match(r[*it])==1)
{
l[x]=*it;
r[*it]=x;
return 1;
}
return 0;
}
bool BF()
{
for(int i=0;i<=D;++i)
been[i]=0,A[i]=-1,dis[i]=inf;
Q.push(S);
been[S]=1;
dis[S]=0;
A[S]=S;
while(!Q.empty())
{
int x=Q.top();
Q.pop();
been[x]=0;
for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
if(C[x][*it]>F[x][*it]&&dis[x]+cost[x][*it]<dis[*it])
{
dis[*it]=dis[x]+cost[x][*it];
A[*it]=x;
if(been[*it]==1)
continue;
Q.push(*it);
been[*it]=1;
}
}
return A[D]!=-1;
}
int main()
{
f>>n;
for(i=0;i<n;++i)
f>>a[i].x>>a[i].y;
for(i=0;i<n;++i)
f>>b[i].x>>b[i].y;
S=2*n;
D=2*n+1;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
cost[j+n][i]=-(cost[i][j+n]=m[++k]=dist(a[i],b[j])),C[i][j+n]=1;
sort(m+1,m+k+1);
for(step=1;step<k;step<<=1);
for(p=0;step;step>>=1)
if(p+step<=k)
{
p+=step;
for(i=0;i<n;++i)
E[i].clear(),l[i]=r[i]=-1;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(cost[i][j+n]<=m[p])
E[i].push_back(j);
do
{
ok=0;
memset(been,0,sizeof(been));
for(i=0;i<n;++i)
if(l[i]==-1)
ok|=match(i);
}while(ok);
for(i=0;i<n;++i)
if(l[i]==-1)
break;
if(i==n)
p-=step;
}
++p;
for(i=0;i<n;++i)
E[i].clear(),E[i].push_back(S),
E[S].push_back(i),C[S][i]=1,
E[i+n].push_back(D),E[D].push_back(i+n),C[i+n][D]=1;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
if(cost[i][j+n]<=m[p])
E[i].push_back(j+n),E[j+n].push_back(i);
while(BF())
{
for(i=D;i!=S;i=A[i])
++F[A[i]][i],--F[i][A[i]];
rez+=dis[D];
}
g.setf(ios::fixed,ios::floatfield);
g.precision(5);
g<<m[p]<<" "<<rez<<"\n";
}