Pagini recente » Cod sursa (job #1313438) | Cod sursa (job #2437858) | Cod sursa (job #1352285) | Cod sursa (job #1258719) | Cod sursa (job #2715239)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#define LL long long
using namespace std;
ifstream cin("adapost.in");
ofstream cout("adapost.out");
int N,S,D, ant[840];
short fl[32][840][840];
LL Cst[840][840];
LL inf=2000000001;
queue <int> Q;
LL old_d[840],real_d[840], d[840],aux[840];
int viz[840];
vector <int> G[840];
priority_queue <pair<LL,int>, vector<pair<LL,int> >, greater<pair<LL,int> > > pq;
pair <double,double> soldat[440],adapost[440];
double dist(pair<double,double> A,pair<double,double> B)
{
return sqrt((A.first-B.first)*(A.first-B.first)+
(A.second-B.second)*(A.second-B.second));
}
LL Fm,Fcst;
void bellmanford();
bool djikstra(int ind,LL dmax);
int main()
{
cin>>N;
S=0; D=2*N+1;
for(int i=1; i<=N; ++i)
{
cin>>soldat[i].first>>soldat[i].second;
G[S].push_back(i);
G[i].push_back(S);
for(int lg=0; lg<32; ++lg)
fl[lg][S][i]=1;
}
for(int i=1; i<=N; ++i)
{
cin>>adapost[i].first>>adapost[i].second;
G[D].push_back(i+N);
G[i+N].push_back(D);
for(int lg=0; lg<32; ++lg)
fl[lg][i+N][D]=1;
}
double dbl;
for(int i=1; i<=N; ++i)
for(int j=1; j<=N; ++j)
{
for(int lg=0; lg<32; ++lg)
fl[lg][i][j+N]=1;
G[i].push_back(j+N);
G[j+N].push_back(i);
dbl=dist(soldat[i],adapost[j])*1000000;
Cst[i][j+N]=(LL)dbl;
Cst[j+N][i]=-Cst[i][j+N];
}
bellmanford();
LL st,dr,mij,sol=inf,sol2=inf;
int k=-1;
st=0; dr=inf; mij=0;
while(st<=dr)
{
mij=(st+dr)/2;
Fm=0; Fcst=0;
k++;
for(int i=0; i<=D; ++i)
old_d[i]=aux[i];
while(djikstra(k,mij));
if(Fm==N)
{
sol=mij; dr=mij-1; sol2=Fcst;
}
else st=mij+1;
}
double dbl2;
dbl=(double)sol/1000000;
dbl2=(double)sol2/1000000;
cout<<setprecision(6)<<dbl<<' '<<dbl2<<'\n';
return 0;
}
void bellmanford()
{
int nod;
LL new_d;
for(int i=0; i<=D; ++i)
aux[i]=inf;
viz[S]=1; aux[S]=0;
Q.push(S);
while(!Q.empty())
{
nod=Q.front(); Q.pop(); viz[nod]=0;
if(nod==D)
continue;
for(auto nn:G[nod])
if(fl[0][nod][nn])
{
new_d=aux[nod]+Cst[nod][nn];
if(new_d<aux[nn])
{
aux[nn]=new_d;
if(!viz[nn])
{
viz[nn]=1;
Q.push(nn);
}
}
}
}
}
bool djikstra(int ind,LL dmax)
{
int nod; LL cost, new_d;
for(int i=0; i<=D; ++i)
d[i]=inf, ant[i]=i;
d[S]=real_d[S]=0;
pq.push({0,S});
while(!pq.empty())
{
nod=pq.top().second;
cost=pq.top().first;
pq.pop();
if(d[nod]!=cost)
continue;
for(auto nn:G[nod])
if(fl[ind][nod][nn] && Cst[nod][nn] <=dmax)
{
new_d=old_d[nod]-old_d[nn]+Cst[nod][nn]+d[nod];
if(new_d<d[nn])
{
d[nn]=new_d;
real_d[nn]=real_d[nod]+Cst[nod][nn];
ant[nn]=nod;
pq.push({d[nn],nn});
}
}
}
if(d[D]==inf)
return 0;
for(nod=0; nod<=D; ++nod) old_d[nod]=real_d[nod];
LL Fmin=inf,total=0;
for(nod=D; nod!=S; nod=ant[nod])
{
Fmin=min(Fmin, 1ll*fl[ind][ant[nod]][nod]);
total+=Cst[ant[nod]][nod];
}
Fm+=Fmin;
Fcst+=total;
for(nod=D; nod!=S; nod=ant[nod])
{
fl[ind][ant[nod]][nod]-=Fmin;
fl[ind][nod][ant[nod]]+=Fmin;
}
return 1;
}