Cod sursa(job #1517766)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 4 noiembrie 2015 20:05:22
Problema Adapost Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.66 kb
#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!