Cod sursa(job #1517761)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 4 noiembrie 2015 19:45:40
Problema Adapost Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.43 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;

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!