Pagini recente » Cod sursa (job #2488240) | Cod sursa (job #1771875) | Cod sursa (job #2648176) | Cod sursa (job #2831543) | Cod sursa (job #2242869)
#include <bits/stdc++.h>
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n;
const int MAXN = 810;
const int source = 0;
const int target = 801;
const double eps = 1e-5;
int currentFlow[MAXN][MAXN];
int capacity[MAXN][MAXN];
pair< double, double > sold[MAXN];
pair< double, double > ad[MAXN];
double cost[MAXN][MAXN];
double dist[MAXN];
double potential[MAXN];
int tata[MAXN];
vector< int > gr[MAXN];
double d(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));
}
class cmp {
public:
const bool operator() (const pair< int , double > &a, const pair< int, double > &b) const {
return a.second > b.second;
}
};
priority_queue< pair< int, double >, vector< pair< int, double > >, cmp > H;
bool dijkstra (double lim) {
H.push(make_pair(source, 0));
for(int i = 1; i <= target; ++i) dist[i] = 1e9;
tata[target] = 0;
while(H.size()) {
int node;
double curcost;
tie(node, curcost) = H.top();
H.pop();
if(curcost != dist[node]) continue;
for(auto &i : gr[node]) {
if(currentFlow[node][i] < capacity[node][i] && cost[node][i] < lim + eps &&
curcost + cost[node][i] + potential[node] - potential[i] < dist[i]) {
dist[i] = curcost + cost[node][i] + potential[node] - potential[i];
tata[i] = node;
H.push(make_pair(i, dist[i]));
}
}
}
memcpy(potential, dist, sizeof potential);
return (tata[target] != 0);
}
double flowCost = 0;
double totalFlow = 0;
bool perfectMatching(double lim) {
while(dijkstra(lim)) {
int node = target;
int minim = 1e9;
while(node) {
minim = min(minim, capacity[tata[node]][node] - currentFlow[tata[node]][node]);
node = tata[node];
}
node = target;
while(node) {
currentFlow[tata[node]][node] += minim;
currentFlow[node][tata[node]] -= minim;
node = tata[node];
}
totalFlow += minim;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(currentFlow[i][n + j]) flowCost += cost[i][n + j];
}
}
return (totalFlow == n);
}
int lft[MAXN], rght[MAXN];
bool vizz[MAXN];
int cnt = 0;
bool cuplaj(int node, double lim) {
if(vizz[node]) return false;
vizz[node] = true;
for(auto &x : gr[node]) {
if(!lft[x] && cost[node][x] < lim + eps) {
lft[x] = node;
rght[node] = x;
++cnt;
return true;
}
}
for(auto &x : gr[node]) {
if(cost[node][x] < lim + eps && cuplaj(lft[x], lim)) {
lft[x] = node;
rght[node] = x;
return true;
}
}
return false;
}
bool ok(double lim) {
memset(lft, 0, sizeof lft);
memset(rght, 0, sizeof rght);
lft[0] = -1;
cnt = 0;
bool k = true;
while(k) {
k = false;
memset(vizz, 0, sizeof vizz);
for(int i = 1; i <= n; ++i) {
if(!rght[i]) k |= cuplaj(i, lim);
}
}
return (cnt == n);
}
int main(){
f >> n;
for(int i = 1; i <= n; ++i) {
f >> sold[i].first >> sold[i].second;
}
for(int i = 1; i <= n; ++i) {
f >> ad[i].first >> ad[i].second;
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
gr[i].emplace_back(n + j);
gr[n + j].emplace_back(i);
cost[i][n + j] = d(sold[i], ad[j]);
cost[n + j][i] = -d(sold[i], ad[j]);
capacity[i][n + j] = 1;
}
}
for(int i = 1; i <= n; ++i) {
gr[source].emplace_back(i);
gr[i].emplace_back(source);
gr[i + n].emplace_back(target);
gr[target].emplace_back(i + n);
capacity[source][i] = 1;
capacity[i + n][target] = 1;
}
double ans = -1;
double lo = 0, hi = 1500;
while(abs(lo - hi) > eps) {
double mid = (lo + hi) / 2;
if(ok(mid)) {
ans = mid;
hi = mid;
} else {
lo = mid;
}
}
perfectMatching(ans);
g.precision(10);
g << fixed;
g << ans << ' ' << flowCost;
return 0;
}