Pagini recente » Cod sursa (job #2681143) | Cod sursa (job #446031) | Cod sursa (job #3193018) | Cod sursa (job #1579945) | Cod sursa (job #1517761)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#define DIM 815
#define INF 1000000010
#define infile "adapost.in"
#define outfile "adapost.out"
using namespace std;
const double eps = 1e-5;
int n;
vector<int> graph[DIM];
vector<double> edgesCosts;
int capacity[DIM][DIM], flow[DIM][DIM];
double x[DIM], y[DIM];
double cost[DIM][DIM];
int parent[DIM];
double dist[DIM], newDist[DIM], dijDist[DIM];
bool inQue[DIM];
class Comp {
public:
bool operator()(const pair<int, double> &a, const pair<int, double> &b) {
return a.second > b.second;
}
};
priority_queue< pair<int, double>, vector< pair<int, double> >, Comp > heap;
void bellmanFord(int source, int destination, double maxCost) {
for (int i = source; i <= destination; ++i)
dist[i] = INF, inQue[i] = false;
dist[source] = 0;
queue<int> que;
que.push(source);
while (!que.empty()) {
int curr = que.front();
que.pop();
inQue[curr] = false;
for (int adj : graph[curr]) {
if (dist[adj] <= dist[curr] + cost[curr][adj] || capacity[curr][adj] == flow[curr][adj] || maxCost + eps < cost[curr][adj])
continue;
dist[adj] = dist[curr] + cost[curr][adj];
if (inQue[adj])
continue;
inQue[adj] = true;
que.push(adj);
}
}
}
bool dijkstra(int source, int destination, double maxCost) {
for (int i = source; i <= destination; ++i)
dijDist[i] = INF, newDist[i] = INF;
dijDist[source] = newDist[source] = 0;
heap.push(make_pair(source, 0));
while (!heap.empty()) {
int curr = heap.top().first;
double cst = heap.top().second;
heap.pop();
if (dijDist[curr] != cst)
continue;
for (int adj : graph[curr]) {
if (capacity[curr][adj] == flow[curr][adj] || maxCost + eps < cost[curr][adj])
continue;
double temp = dijDist[curr] + cost[curr][adj] + dist[curr] - dist[adj];
if (temp < dijDist[adj]) {
dijDist[adj] = temp;
newDist[adj] = newDist[curr] + cost[curr][adj];
parent[adj] = curr;
heap.push(make_pair(adj, temp));
}
}
}
memcpy(dist, newDist, sizeof dist);
return dist[destination] != INF;
}
double getDist(int a, int b) {
return sqrt((x[a] - x[b])*(x[a] - x[b]) + (y[a] - y[b])*(y[a] - y[b]));
}
int main() {
ifstream fin(infile);
ofstream fout(outfile);
fin >> n;
for (int i = 1; i <= 2 * n; ++i) {
fin >> x[i] >> y[i];
}
int source = 0, destination = 2 * n + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int a = i;
int b = j + n;
capacity[a][b] = 1;
cost[a][b] = getDist(a, b);
cost[b][a] = -cost[a][b];
edgesCosts.push_back(cost[a][b]);
graph[a].push_back(b);
graph[b].push_back(a);
}
}
for (int i = 1; i <= n; ++i) {
capacity[source][i] = 1;
graph[source].push_back(i);
graph[i].push_back(source);
capacity[i + n][destination] = 1;
graph[destination].push_back(i + n);
graph[i + n].push_back(destination);
}
sort(edgesCosts.begin(), edgesCosts.end());
//------------------------------------------------------------------------
int left = 0, right = (int)edgesCosts.size() - 1;
double maxEdgeCost = 0, minTotalCost = INF;
while (left <= right) {
int middle = (left + right) / 2;
memset(flow, 0, sizeof flow);
bellmanFord(source, destination, edgesCosts[middle]);
double totalCost = 0;
int maxFlow = 0;
while (dijkstra(source, destination, edgesCosts[middle])) {
int addFlow = INF;
for (int curr = destination; curr != source; curr = parent[curr]) {
addFlow = min(addFlow, capacity[parent[curr]][curr] - flow[parent[curr]][curr]);
}
maxFlow += addFlow;
totalCost += addFlow * dist[destination];
for (int curr = destination; curr != source; curr = parent[curr]) {
flow[parent[curr]][curr] += addFlow;
flow[curr][parent[curr]] -= addFlow;
}
}
if (maxFlow == n) {
maxEdgeCost = edgesCosts[middle];
minTotalCost = totalCost;
right = middle - 1;
}
else {
left = middle + 1;
}
}
//------------------------------------------------------------------------
fout << setprecision(5) << fixed << maxEdgeCost << ' ';
fout << setprecision(5) << fixed << minTotalCost << '\n';
return 0;
}
//Trust me, I'm the Doctor!