Pagini recente » Cod sursa (job #1058921) | Cod sursa (job #535761) | Cod sursa (job #1953256) | Cod sursa (job #3201116) | Cod sursa (job #2932934)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("adapost.in");
ofstream out("adapost.out");
#endif
const int nmax = 405;
int n,cap[nmax][nmax];
double cost[nmax][nmax];
int flow[nmax][nmax];
pair<double,double>sold[nmax],adap[nmax];
vector<vector<pair<int,double>>> g;
double square(double a) {
return a * a;
}
double dist2(pair<double,double> a, pair<double,double> b) {
return sqrt(square(a.first - b.first) + square(a.second - b.second));
}
const int inf = 1000000005;
double find_augmenting_path() {
priority_queue<pair<double,int>> q;
q.push({0 , 0});
vector<double> myDis(2 * n + 2, inf);
myDis[0] = 0;
vector<int> path(2 * n + 2, 0);
while(!q.empty()) {
double val = -q.top().first;
int node = q.top().second;
q.pop();
if (val > myDis[node]) continue;
for (auto k : g[node]) {
double costEdge = cost[node][k.first];
if (myDis[k.first] > myDis[node] + costEdge && flow[node][k.first] < cap[node][k.first]) {
myDis[k.first] = myDis[node] + costEdge;
path[k.first] = node;
q.push({-myDis[k.first], k.first});
}
}
}
if (path[2 * n + 1] == 0) {
return -1;
}
int node = 2 * n + 1,bottle_neck = inf;
while(node != 0) {
int from = path[node];
bottle_neck = min(bottle_neck , cap[from][node] - flow[from][node]);
node = from;
}
node = 2 * n + 1;
double cur_cost = 0;
while(node != 0) {
int from = path[node];
flow[from][node] += bottle_neck;
flow[node][from] -= bottle_neck;
cur_cost += cost[from][node];
node = from;
}
return cur_cost;
}
double maxflow() {
double total_cost = 0;
while(true) {
double added_cost = find_augmenting_path();
if (added_cost == -1) {
return total_cost;
}
total_cost += added_cost;
}
return total_cost;
}
int main() {
in >> n;
g.resize(2 * n + 2);
for (int i =1 ; i <= n; i++) {
in >> sold[i].first >> sold[i].second;
}
for (int i =1 ; i <= n; i++) {
in >> adap[i].first >> adap[i].second;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
double ds = dist2(sold[i], adap[j]);
g[i].push_back({j + n, ds});
g[j + n].push_back({i, -ds});
cost[i][j + n] = ds;
cost[j + n][i] = -ds;
cap[i][j + n] = 1;
}
}
for (int i = 1; i <= n; i++) {
g[0].push_back({i, 0});
g[i].push_back({0, 0});
cap[0][i] = 1;
}
for (int i = n + 1; i <= n * 2; i++) {
cap[i][2 * n + 1] = 1;
g[i].push_back({2 * n + 1, 0});
g[2 * n + 1].push_back({i, 0});
}
double maxval = maxflow();
double maxedge = -inf;
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= 2 * n; j++) {
if (flow[i][j] == 1) {
maxedge = max(maxedge , cost[i][j]);
}
}
}
out << fixed << setprecision(6) << maxedge << " " << maxval << "\n";
}