Pagini recente » Cod sursa (job #1395436) | Cod sursa (job #16955) | Cod sursa (job #2800496) | Cod sursa (job #2407429) | Cod sursa (job #2588318)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const double EPS = 0.0001;
const double INF = 1e9;
struct Edge
{
int x;
int y;
int cap;
double cost;
int cap1;
};
vector <Edge> edges;
vector <vector <int> > adj;
vector <double> dist;
vector <double> cost;
vector <int> dad;
int n, S, D;
void add_edge(int x, int y, int c, double z)
{
adj[x].emplace_back(edges.size());
edges.emplace_back(Edge{x, y, c, z, c});
adj[y].emplace_back(edges.size());
edges.emplace_back(Edge{y, x, 0, -z, 0});
}
void bellman_ford()
{
vector <bool> inQ(n + 1, false);
queue <int> q;
q.push(S);
inQ[S] = true;
dist[S] = 0;
while(!q.empty())
{
int nod = q.front();
q.pop();
inQ[nod] = false;
for(auto i : adj[nod])
{
if(edges[i].cap && dist[edges[i].y] > dist[nod] + edges[i].cost)
{
dist[edges[i].y] = dist[nod] + edges[i].cost;
if(!inQ[edges[i].y])
{
inQ[edges[i].y] = true;
q.push(edges[i].y);
}
}
}
}
}
priority_queue <pair <double, int> > pq;
bool dijkstra()
{
for(int i = 1; i <= n; ++i)
{
dad[i] = -1;
cost[i] = INF;
}
cost[S] = 0;
pq.push({0, S});
while(!pq.empty())
{
int nod = pq.top().second;
double val = pq.top().first;
pq.pop();
if(val != -cost[nod])
{
continue;
}
for(auto i : adj[nod])
{
if(edges[i].cap && cost[edges[i].y] > cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost)
{
cost[edges[i].y] = cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost;
pq.push({-cost[edges[i].y], edges[i].y});
dad[edges[i].y] = i;
}
}
}
for(int i = 1; i <= n; i++)
{
dist[i] += cost[i];
}
return (dad[D] != -1);
}
void reset(double limit)
{
for(auto& i : edges)
{
i.cap = i.cap1;
if(i.cost > limit || -i.cost > limit)
i.cap = 0;
}
for(auto& i : dist)
i = INF;
}
pair <int, double> get_flow(double limit)
{
reset(limit);
bellman_ford();
double cost = 0;
int cap = 0;
while(dijkstra())
{
int cat = INF;
for(int i = dad[D]; i != -1; i = dad[edges[i].x])
cat = min(cat, edges[i].cap);
for(int i = dad[D]; i != -1; i = dad[edges[i].x])
{
cost += cat * edges[i].cost;
edges[i].cap -= cat;
int p = i;
edges[p ^ 1].cap += cat;
}
cap += cat;
}
return {cap, cost};
}
const int DIM = 401;
double x[DIM * 2];
double y[DIM * 2];
double get_cost(int i, int j)
{
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
main()
{
int n;
fin >> n;
::n = 2 * n + 2;
adj.resize(2 * n + 3);
dad.resize(2 * n + 3);
cost.resize(2 * n + 3);
dist.resize(2 * n + 3);
for(int i = 1; i <= 2 * n; ++i)
{
fin >> x[i] >> y[i];
}
S = 2 * n + 1;
D = 2 * n + 2;
for(int i = 1; i <= n; ++i)
for(int j = n + 1; j <= n + n; ++j)
{
add_edge(i, j, 1, get_cost(i, j));
}
for(int i = 1; i <= n; ++i)
{
add_edge(2 * n + 1, i, 1, 0);
add_edge(i + n, 2 * n + 2, 1, 0);
}
double l = 0;
double r = 1e3;
pair <double, double> ans;
while(l + EPS < r)
{
double mid = (l + r) / 2;
pair <int, double> res = get_flow(mid);
if(res.first == n)
{
ans = {mid, res.second};
r = mid - EPS;
}
else
{
l = mid + EPS;
}
}
fout << fixed << setprecision(3) << ans.first << ' ' << ans.second << '\n';
}