Pagini recente » Cod sursa (job #2164643) | Cod sursa (job #1532915) | 24hours | Cod sursa (job #1389640) | Cod sursa (job #1662327)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
#include <queue>
using namespace std;
const int NMAX = 405;
int n;
struct point {
double x, y;
point(double _x = 0, double _y = 0): x(_x), y(_y) {}
} soldati[NMAX], adaposturi[NMAX];
double dist(const point &a, const point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
pair <double, pair <int, int> > all_dists[NMAX * NMAX];
vector <int> matching_graph[NMAX];
int _left[NMAX];
int _right[NMAX];
bitset <2 * NMAX> vis;
void build_matching_graph(int edges_count) {
for (int i = 1; i <= edges_count; ++ i)
matching_graph[all_dists[i].second.first].push_back(all_dists[i].second.second);
}
void destruct_matching_graph(int edges_count) {
for (int i = 1; i <= edges_count; ++ i)
matching_graph[all_dists[i].second.first].clear();
}
bool pair_up(int node) {
if (vis[node])
return false;
vis[node] = true;
for (auto it: matching_graph[node])
if (!_right[it]) {
_left[node] = it;
_right[it] = node;
return true;
}
for (auto it: matching_graph[node])
if (pair_up(_right[it])) {
_left[node] = it;
_right[it] = node;
return true;
}
return false;
}
int maximum_matching() {
memset(_left, 0, sizeof _left);
memset(_right, 0, sizeof _right);
bool done = false;
while (!done) {
done = true;
vis &= 0;
for (int i = 1; i <= n; ++ i)
if (!_left[i] && pair_up(i))
done = false;
}
int matching_count = 0;
for (int i = 1; i <= n; ++ i)
matching_count += (bool)_left[i];
return matching_count;
}
//Mincost Maxflow
int N, s, t;
vector <int> graph[2 * NMAX];
int cap[2 * NMAX][2 * NMAX];
double cost[2 * NMAX][2 * NMAX];
void add_edge(int a, int b, double c) {
graph[a].push_back(b);
graph[b].push_back(a);
cap[a][b] = 1;
cost[a][b] += c;
cost[b][a] -= c;
}
queue <int> _queue;
bool in_queue[2 * NMAX];
double potentials[2 * NMAX];
const double INF = 1e14;
void bellman(){
for (int i = 1; i <= N; ++ i) {
in_queue[i] = false;
potentials[i] = INF;
}
in_queue[s] = true;
potentials[s] = 0;
_queue.push(s);
int node;
while (!_queue.empty()) {
node = _queue.front();
_queue.pop();
in_queue[node] = false;
for (auto it: graph[node])
if (cap[node][it] && potentials[node] + cost[node][it] < potentials[it]) {
potentials[it] = potentials[node] + cost[node][it];
if (!in_queue[it]) {
_queue.push(it);
in_queue[it] = true;
}
}
}
}
priority_queue <pair <double, int>, vector <pair <double, int> >, greater <pair <double, int> > > _priority_queue;
double d[2 * NMAX];
int father[2 * NMAX];
bool dijkstra() {
for (int i = 1; i <= N; ++ i)
d[i] = INF;
_priority_queue.push(make_pair(0, s));
d[s] = 0;
vis &= 0;
int node;
while (!_priority_queue.empty()) {
node = _priority_queue.top().second;
_priority_queue.pop();
if (vis[node])
continue;
vis[node] = true;
for (auto it: graph[node])
if (cap[node][it] && d[node] + cost[node][it] + potentials[node] - potentials[it] < d[it]) {
d[it] = d[node] + cost[node][it] + potentials[node] - potentials[it];
father[it] = node;
_priority_queue.push(make_pair(d[it], it));
}
}
return vis[t];
}
double mincost_flow() {
bellman();
double ans = 0;
while (dijkstra()) {
int node = t;
while (father[node]) {
cap[father[node]][node] -= 1;
cap[node][father[node]] += 1;
ans += cost[father[node]][node];
node = father[node];
}
for (int i = 1; i <= N; ++ i)
d[i] -= (potentials[s] - potentials[i]);
memcpy(potentials, d, sizeof(double) * (N + 2));
}
return ans;
}
int main()
{
ifstream cin("adapost.in");
ofstream cout("adapost.out");
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> soldati[i].x >> soldati[i].y;
for (int i = 1; i <= n; ++ i)
cin >> adaposturi[i].x >> adaposturi[i].y;
int pos = 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
all_dists[++ pos] = make_pair(dist(soldati[i], adaposturi[j]), make_pair(i, j));
sort(all_dists + 1, all_dists + pos + 1);
int st = 1;
int dr = pos - 1;
int mid;
int ans = pos;
while (st <= dr) {
mid = (st + dr) >> 1;
build_matching_graph(mid);
if (maximum_matching() == n) {
ans = mid;
dr = mid - 1;
}
else
st = mid + 1;
destruct_matching_graph(mid);
}
cout << fixed << setprecision(5) << all_dists[ans].first << ' ';
//Construim graful de flux
for (int i = 1; i <= ans; ++ i)
add_edge(all_dists[i].second.first, n + all_dists[i].second.second, all_dists[i].first);
s = 2 * n + 1;
t = 2 * n + 2;
N = t;
for (int i = 1; i <= n; ++ i) {
add_edge(s, i, 0);
add_edge(n + i, t, 0);
}
cout << mincost_flow() << '\n';
cin.close();
cout.close();
return 0;
}