Cod sursa(job #2588286)

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

using namespace std;

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

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

struct Network
{
	vector <Edge> edges;
	vector <vector <int> > adj;
	
	vector <double> dist;
	
	int n, S, D;
	
	Network(int n, int S, int D) : n(n), S(S), D(D), adj(n + 1), dist(n + 1, INF) {}
	
	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;
	
	for(int i = 1; i <= 2 * n; ++i)
	{
		fin >> x[i] >> y[i];
	}
	
	Network retea(2 * n + 2, 2 * n + 1, 2 * n + 2);
	
	for(int i = 1; i <= n; ++i)
		for(int j = n + 1; j <= n + n; ++j)
		{
			retea.add_edge(i, j, 1, get_cost(i, j));
		}
	
	for(int i = 1; i <= n; ++i)
	{
		retea.add_edge(2 * n + 1, i, 1, 0);
		retea.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 = retea.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';
}