Pagini recente » Cod sursa (job #653950) | Cod sursa (job #1102255) | Cod sursa (job #1105824) | Cod sursa (job #2402494) | Cod sursa (job #2081325)
#include <bits/stdc++.h>
using namespace std;
const int maxN=405;
const int INF=0x3f3f3f3f;
const double EPS=1e-7;
bool vis[maxN];
int _left[maxN],_right[maxN];
double dist[2*maxN];
int t[2*maxN];
vector<int> v[2*maxN];
int flow[2*maxN][2*maxN];
double cost[2*maxN][2*maxN];
bool cap[2*maxN][2*maxN];
double sol;
int n,source,sink;
pair<double,double> man[maxN],house[maxN];
vector<double> distances;
bool pairup(int nod,double maxEdge)
{
if(vis[nod])
return false;
vis[nod]=true;
for(int i=1;i<=n;i++)
if(cost[nod][n+i]<=maxEdge && !_right[i]){
_right[i]=nod;
_left[nod]=i;
return true;
}
for(int i=1;i<=n;i++)
if(cost[nod][n+i]<=maxEdge && pairup(_right[i],maxEdge)){
_right[i]=nod;
_left[nod]=i;
return true;
}
return false;
}
bool perfectMatch(double maxEdge)
{
memset(_left,0,sizeof(_left));
memset(_right,0,sizeof(_right));
bool ok=true;
while(ok)
{
ok=false;
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
if(!_left[i] && pairup(i,maxEdge))
ok=true;
}
for(int i=1;i<=n;i++)
if(!_left[i])
return false;
return true;
}
bool bellmanford()
{
memset(t,0,sizeof(t));
bitset<2*maxN> inQue;
queue<int> Que;
for(int i=1;i<=2*n+1;i++)
dist[i]=INF;
dist[source]=0;
Que.push(source);
inQue[source]=true;
while(!Que.empty())
{
int nod=Que.front();
Que.pop();
inQue[nod]=false;
for(auto it:v[nod])
if(flow[nod][it]<cap[nod][it] && cost[nod][it]<=sol && dist[it]>dist[nod]+cost[nod][it]){
dist[it]=dist[nod]+cost[nod][it];
t[it]=nod;
if(!inQue[it]){
Que.push(it);
inQue[it]=true;
}
}
}
return dist[sink]<INF;
}
int main()
{
ifstream f("adapost.in");
ofstream g("adapost.out");
f>>n;
sink=2*n+1;
for(int i=1;i<=n;i++)
f>>man[i].first>>man[i].second;
for(int i=1;i<=n;i++)
f>>house[i].first>>house[i].second;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
double x=man[i].first-house[j].first;
double y=man[i].second-house[j].second;
double edge=sqrt(x*x+y*y);
cost[i][j+n]=edge;
cost[j+n][i]=-edge;
distances.push_back(edge);
}
sort(distances.begin(),distances.end());
int st=0,dr=n*n;
while(st<=dr)
{
int mij=(st+dr)/2;
if(perfectMatch(distances[mij])){
sol=distances[mij];
dr=mij-1;
}
else st=mij+1;
}
for(int i=1;i<=n;i++){
cap[source][i]=1;
v[source].push_back(i);
v[i].push_back(source);
cap[i+n][sink]=1;
v[i+n].push_back(sink);
v[sink].push_back(i+n);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(cost[i][j]<=sol){
v[i].push_back(j);
v[j].push_back(i);
cap[i][j]=1;
}
double mincost=0;
while(bellmanford()){
for(int nod=sink;nod!=source;nod=t[nod]){
flow[t[nod]][nod]++;
flow[nod][t[nod]]--;
}
mincost+=dist[sink];
}
g<<setprecision(5)<<fixed<<sol<<" "<<mincost;
return 0;
}