Pagini recente » Cod sursa (job #729058) | Cod sursa (job #2128386) | Cod sursa (job #1875149) | Cod sursa (job #1296986) | Cod sursa (job #1517766)
#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;
int leftMatch[DIM], rightMatch[DIM];
bool visited[DIM];
bool canMatch(int node) {
if (visited[node])
return false;
visited[node] = true;
for (int adj : graph[node]) {
if (!rightMatch[adj]) {
leftMatch[node] = adj;
rightMatch[adj] = node;
return true;
}
}
for (int adj : graph[node]) {
if (canMatch(rightMatch[adj])) {
leftMatch[node] = adj;
rightMatch[adj] = node;
return true;
}
}
return false;
}
int maxMatch() {
bool ok;
int maximumMatching = 0;
memset(leftMatch, 0, sizeof leftMatch);
memset(rightMatch, 0, sizeof rightMatch);
do {
memset(visited, false, sizeof visited);
ok = false;
for (int i = 1; i <= n; ++i) {
if (!leftMatch[i] && canMatch(i)) {
ok = true;
maximumMatching++;
}
}
} while (ok);
return maximumMatching;
}
void bellmanFord(int source, int destination) {
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])
continue;
dist[adj] = dist[curr] + cost[curr][adj];
if (inQue[adj])
continue;
inQue[adj] = true;
que.push(adj);
}
}
}
bool dijkstra(int source, int destination) {
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])
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]);
}
}
//------------------------------------------------------------------------
sort(edgesCosts.begin(), edgesCosts.end());
double maxEdgeCost = 0;
int left = 0, right = (int)edgesCosts.size() - 1;
while (left <= right) {
int middle = (left + right) / 2;
for (int i = 1; i <= 2 * n; ++i)
graph[i].clear();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int a = i, b = j + n;
if (cost[a][b] > eps + edgesCosts[middle])
continue;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
if (maxMatch() == n) {
right = middle - 1;
maxEdgeCost = edgesCosts[middle];
}
else {
left = middle + 1;
}
}
//------------------------------------------------------------------------
for (int i = 1; i <= 2 * n; ++i)
graph[i].clear();
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);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int a = i, b = j + n;
if (cost[a][b] > eps + maxEdgeCost)
continue;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
bellmanFord(source, destination);
double totalCost = 0;
int maxFlow = 0;
while (dijkstra(source, destination)) {
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;
}
}
//------------------------------------------------------------------------
fout << setprecision(5) << fixed << maxEdgeCost << ' ';
fout << setprecision(5) << fixed << totalCost << '\n';
return 0;
}
//Trust me, I'm the Doctor!