Pagini recente » Cod sursa (job #861549) | Cod sursa (job #153772) | Cod sursa (job #676789) | Cod sursa (job #1608824) | Cod sursa (job #2387233)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <cmath>
#include <bitset>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
ifstream si("adapost.in");
ofstream so("adapost.out");
int n, m, S, D, x, y, c, z, tata[805], cap[805][805];
double flxmax,d[805],real_d[805],dist[805],cost[805][805];
vector<int> v[805];
int ST[405],DR[405],pleis[405][405];
vector<pair<double,pair<int,int> > > u;
bitset<405> viz;
struct neim{
double x,y;
};
neim sold[405],adap[405];
void bellman() {
memset(dist,127,sizeof(dist));
bitset<360> in;
in.reset();
dist[S]=0;
in[S]=1;
queue<int> q;
q.push(S);
while(q.size()) {
int x=q.front();
q.pop();
in[x]=0;
for(auto it:v[x])
if(cap[x][it])
if(dist[it]>dist[x]+cost[x][it])
{
dist[it]=dist[x]+cost[x][it];
if(!in[it])
q.push(it);
in[it]=1;
}
}
}
bool djikstra()
{
memset(d,127,sizeof(d));
memset(real_d,127,sizeof(real_d));
memset(tata,0,sizeof(tata));
priority_queue<pair<int,int> > q;
d[S]=real_d[S]=0;
q.push({0,S});
while(q.size()) {
int y=-q.top().first, x=q.top().second;
q.pop();
if(y>d[x]) continue;
for(auto it:v[x])
if(cap[x][it])
if(d[it]>d[x]+cost[x][it]+dist[x]-dist[it]) {
d[it]=d[x]+cost[x][it]+dist[x]-dist[it];
real_d[it]=real_d[x]+cost[x][it];
q.push({-d[it],it});tata[it]=x;
}
}
for(int i=1; i<=n; i++)
dist[i]=real_d[i];
if(dist[D]>1e9)
return 0;
int ke=1e9;
for(int x=D; tata[x]; x=tata[x])
ke=min(ke,cap[tata[x]][x]);
for(int x=D; tata[x]; x=tata[x]) {
cap[tata[x]][x]-=ke;
cap[x][tata[x]]+=ke;
}
flxmax+=ke*dist[D];
return 1;
}
bool tri(int poz) {
if(viz[poz])
return 0;
viz[poz]=1;
for(auto it:v[poz])
if(!DR[it]) {
ST[poz]=it;
DR[it]=poz;
return 1;
}
for(auto it:v[poz])
if(tri(DR[it])) {
ST[poz]=it;
DR[it]=poz;
return 1;
}
return 0;
}
bool okcup(int mi) {
int ret=0;
for(int i=0; i<mi; i++)
v[u[i].second.first].push_back(u[i].second.second);
memset(ST,0,sizeof(ST));
memset(DR,0,sizeof(DR));
bool ok=1;
while(ok) {
ok=0;
viz.reset();
for(int i=1; i<=n; i++)
if(!ST[i])
if(tri(i)) {
ret++;
ok=1;
}
}
for(int i=1; i<=n; i++)
v[i].resize(0);
return (ret==n);
}
int main() {
si>>n;
for(int i=1; i<=n; i++)
si>>sold[i].x>>sold[i].y;
for(int i=1; i<=n; i++)
si>>adap[i].x>>adap[i].y;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
u.push_back({sqrt((sold[i].x-adap[j].x)*(sold[i].x-adap[j].x)
+(sold[i].y-adap[j].y)*(sold[i].y-adap[j].y)),{i,j}});
sort(u.begin(), u.end());
for(int i=0; i<u.size(); i++)
pleis[u[i].second.first][u[i].second.second]=i+1;
int lo=1, hi=u.size();
while(lo<hi) {
int mi=(lo+hi)/2;
if(okcup(mi))
hi=mi;
else
lo=mi+1;
}
so<<fixed<<setprecision(10)<<u[lo-1].first<<' ';
S=1;
D=2*n+2;
for(int i=2; i<=n+1; i++)
{
v[1].push_back(i);
v[i].push_back(1);
cap[1][i]=1;
}
for(int i=n+2; i<=2*n+1; i++)
{
v[i].push_back(2*n+2);
v[2*n+2].push_back(i);
cap[i][2*n+2]=1;
}
for(int i=0; i<lo; i++)
{
int x=u[i].second.first+1, y=u[i].second.second+n+1;
double z=u[i].first;
v[x].push_back(y);
v[y].push_back(x);
cap[x][y]=1;
cost[x][y]=z;
cost[y][x]=-z;
}
n=2*n+2;
bellman();
for(;djikstra(););
so<<fixed<<setprecision(10)<<flxmax;
return 0;
}