Cod sursa(job #2588296)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 24 martie 2020 17:03:05
Problema Adapost Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("adapost.in");
ofstream fout("adapost.out");

const double EPS = 0.0005;
const double INF = 1e9;
 
struct Edge 
{
	int x;
	int y;
	int cap;
	double cost;
	int cap1;
};

vector <Edge> edges;
vector <vector <int> > adj;
vector <double> dist;
int n, S, D;

void add_edge(int x, int y, int c, double z)
{
	adj[x].emplace_back(edges.size());
	edges.emplace_back(Edge{x, y, c, z, c});

	adj[y].emplace_back(edges.size());
	edges.emplace_back(Edge{y, x, 0, -z, 0});
}

void bellman_ford()
{
	vector <bool> inQ(n + 1, false);
	queue <int> q;
	
	q.push(S);
	inQ[S] = true;
	
	dist[S] = 0;
	
	while(!q.empty()) 
	{
		int nod = q.front();
		q.pop();
		
		inQ[nod] = false;
		
		for(auto i : adj[nod]) 
		{
			if(edges[i].cap && dist[edges[i].y] > dist[nod] + edges[i].cost) 
			{
				dist[edges[i].y] = dist[nod] + edges[i].cost;
				
				if(!inQ[edges[i].y]) 
				{
					inQ[edges[i].y] = true;
					q.push(edges[i].y);
				}
			}
		}
	}
}

bool dijkstra(vector <int>& dad)
{
	dad = vector <int> (n + 1, -1);
	vector <double> cost(n + 1, INF);
	
	priority_queue <pair <double, int> > pq;
	
	cost[S] = 0;
	
	pq.push({0, S});
	
	while(!pq.empty()) 
	{
		int nod = pq.top().second;
		double val = pq.top().first;
		
		pq.pop();
		
		if(val != -cost[nod]) 
		{
			continue;
		}
		
		for(auto i : adj[nod]) 
		{
			if(edges[i].cap && cost[edges[i].y] > cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost) 
			{
				cost[edges[i].y] = cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost;
				
				pq.push({-cost[edges[i].y], edges[i].y});
				dad[edges[i].y] = i;
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		dist[i] += cost[i];
	}
	
	return (dad[D] != -1);
}

void reset(double limit)
{
	for(auto& i : edges)
	{
		i.cap = i.cap1;
		
		if(i.cost > limit || -i.cost > limit)
			i.cap = 0;
	}
	
	for(auto& i : dist)
		i = INF;
}

pair <int, double> get_flow(double limit)
{
	reset(limit);
	bellman_ford();
	
	double cost = 0;
	int cap = 0;
	vector <int> dad;
	
	while(dijkstra(dad)) 
	{
		int cat = INF;
		
		for(int i = dad[D]; i != -1; i = dad[edges[i].x])
			cat = min(cat, edges[i].cap);
		
		for (int i = dad[D]; i != -1; i = dad[edges[i].x]) 
		{
			cost += cat * edges[i].cost;
			edges[i].cap -= cat;
			
			int p = i;
			edges[p ^ 1].cap += cat;
		}
		
		cap += cat;
	}
	
	return {cap, cost};
}

const int DIM = 401;

double x[DIM * 2];
double y[DIM * 2];

double get_cost(int i, int j)
{
	return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}

main()
{
	int n;
	fin >> n;
	
	::n = 2 * n + 2;
	
	adj.resize(2 * n + 3);
	dist.assign(2 * n + 3, INF);
	
	for(int i = 1; i <= 2 * n; ++i)
	{
		fin >> x[i] >> y[i];
	}
	
	S = 2 * n + 1;
	D = 2 * n + 2;
	
	for(int i = 1; i <= n; ++i)
		for(int j = n + 1; j <= n + n; ++j)
		{
			add_edge(i, j, 1, get_cost(i, j));
		}
	
	for(int i = 1; i <= n; ++i)
	{
		add_edge(2 * n + 1, i, 1, 0);
		add_edge(i + n, 2 * n + 2, 1, 0);
	}
	
	double l = 1;
	double r = 1e9;
	
	pair <double, double> ans;
	
	while(l + EPS < r)
	{
		double mid = (l + r) / 2;
		
		pair <int, double> res = get_flow(mid);
		
		if(res.first == n)
		{
			ans = {mid, res.second};
			r = mid - EPS;
		}
		else
		{
			l = mid + EPS;
		}
	}
	
	fout << fixed << setprecision(5) << ans.first << ' ' << ans.second << '\n';
}