Cod sursa(job #1135717)

Utilizator eukristianCristian L. eukristian Data 8 martie 2014 12:03:12
Problema Adapost Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.18 kb
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

#define MAXN 802
// 0 - source s
// 801 - sink t

int n;

struct coord { double x, y; } soldiers[MAXN], shelters[MAXN];

struct sdist {double dist; int x, y; };

vector<pair<int, double> > G[MAXN];
vector<sdist> distances;

inline double distance(struct coord* a, struct coord* b)
{
	return sqrt((a->x - b->x) * (a->x - b->x) + (a->y - b->y) * (a->y - b->y));
}

bool comp(const sdist& a, const sdist& b)
{
	return a.dist <= b.dist;
}

/* Hopcroft Karp Matching - procedures and data : */
int pairs[MAXN];
int dist[MAXN];
queue<int> que;

int hopcroftKarpMatch();
char hkBFS();
char hkDFS(int nd);

/* END Hopcroft Karp Matching Procedures */

/* Minimum weight max matching */

char inqueue[MAXN], flow[MAXN][MAXN], capacity[MAXN][MAXN];
int prev[MAXN];
double mwDist[MAXN];

double sumMatch();
char bellman();

/* END OF Minimum weight max matching */

double binSearchWeight(int left, int right);

void initGraph(double maxWeight)
{
	for (int i = 1 ; i <= 2 * n ; ++i)
		G[i].clear();
	
	for (vector<sdist>::iterator it = distances.begin() ; it != distances.end() && it->dist <= maxWeight ; ++it)
		G[it->x].push_back(make_pair(it->y, it->dist));
}

int main()
{
	int i, j;
	freopen("adapost.in", "r", stdin);
	freopen("adapost.out","w",stdout);
	scanf("%d", &n);
	
	for (i = 1 ; i <= n ; ++i)
		scanf("%lf %lf", &soldiers[i].x, &soldiers[i].y);
	for (i = 1 ; i <= n ; ++i)
		scanf("%lf %lf", &shelters[i].x, &shelters[i].y);
		
	double lmin, gmax = 0.0;
	for (i = 1 ; i <= n ; ++i)
	{
		lmin = DBL_MAX;
		for (j = 1 ; j <= n ; ++j)
		{
			double dst = distance(soldiers + i, shelters + j);
			if (dst < lmin)
				lmin = dst;
			
			sdist sd = {dst, i, j + n};
			distances.push_back(sd);
			capacity[i][j + n] = 1;
		}
		
		if (lmin > gmax)
			gmax = lmin;
	}
	
	sort(distances.begin(), distances.end(), comp);
	
	int left = 0, right = distances.size() - 1;
	while (left < right)
	{
		int mid = (left + right) >> 1;
		if (distances[mid].dist < gmax)
			left = mid + 1;
		else
			right = mid;
	}
	
	right = distances.size() - 1;
	
	double maxWeight = binSearchWeight(left, right);	
	
	for (int i = 1 ; i <= 2 * n ; ++i)
		G[i].clear();
	for (vector<sdist>::iterator it = distances.begin() ; it != distances.end() && it->dist <= maxWeight ; ++it)
	{
		G[it->x].push_back(make_pair(it->y, it->dist));
		G[it->y].push_back(make_pair(it->x, -it->dist));
	} 
	
	printf("%.5lf %.5lf\n", maxWeight, sumMatch());
	
	return 0;
}

double binSearchWeight(int left, int right)
{
	// assume there is actually a matching of cardinality n
	while (left < right)
	{
		int mid = (left + right) >> 1;
		initGraph(distances[mid].dist);
		if (hopcroftKarpMatch() < n)
			left = mid + 1;
		else
			right = mid;
	}
	
	return distances[right].dist;
}

/* HK implementation */
int hopcroftKarpMatch()
{
	int matching = 0, i;
	memset(pairs, 0, ((n + 1) * sizeof(int)) << 1);
	
	while (hkBFS() == 1)
	{
		for (i = 1 ; i <= n ; ++i)
			if (pairs[i] == 0 && hkDFS(i) == 1)
				matching++;
	}
	
	return matching;
}

char hkBFS()
{
	int i;
	memset(dist, 0x7f, 2 * (n + 1) * sizeof(int));
	for (i = 1 ; i <= n ; ++i)
		if (pairs[i] == 0)
			que.push(i), dist[i] = 0;
			
	while (que.empty() == false)
	{
		int crtNode = que.front(); que.pop();
		if (dist[crtNode] < dist[0])
			for (vector<pair<int, double> >::iterator it = G[crtNode].begin(); it != G[crtNode].end() ; ++it)
			{
				if (dist[pairs[it->first]] == 0x7f7f7f7f)
				{
					dist[pairs[it->first]] = dist[crtNode] + 1;
					que.push(pairs[it->first]);
				}
			} 
	}
	
	if (dist[0] != 0x7f7f7f7f)
		return 1;
	return 0;
}

char hkDFS(int nd)
{
	if (nd == 0)
		return 1;
	for (vector<pair<int, double> >::iterator it = G[nd].begin() ; it != G[nd].end() ; ++it)
	{
		if (dist[pairs[it->first]] == dist[nd] + 1 && hkDFS(pairs[it->first]) == 1)
		{
			pairs[nd] = it->first;
			pairs[it->first] = nd;
			return 1;
		}
	}
	dist[nd] = 0x7f7f7f7f;
	return 0;
}

/*HK implementation end */


double sumMatch()
{
	int i;
	double total = 0;
	for (i = 1 ; i <= n ; ++i)
	{
		G[0].push_back(make_pair(i, 0));
		G[i].push_back(make_pair(0, 0));
		
		G[2*n+1].push_back(make_pair(n+i, 0));
		G[n+i].push_back(make_pair(2*n+1, 0));
		
		capacity[0][i] = 1;
		capacity[i + n][2*n+1] = 1;
	}
	
	while (bellman())
	{
		for (i = 2*n + 1; i != 0 ; i = prev[i])
			flow[prev[i]][i]++, flow[i][prev[i]]--;
		total += mwDist[2*n+1];
	}
	
	return total;
}

char bellman()
{
	int i;
	for (i = 0 ; i <= 2 * n + 1;  ++i) 
	{
		mwDist[i] = 0x7fffffff;
		inqueue[i] = 0;
		prev[i] = -1;
	}
	
	mwDist[0] = 0; inqueue[0] = 1;
	que.push(0);
	
	while (que.empty() == false)
	{
		int crtNode = que.front(); que.pop();
		
		for (vector<pair<int, double> >::iterator it = G[crtNode].begin(); it != G[crtNode].end() ; ++it)
		{
			if (flow[crtNode][it->first] < capacity[crtNode][it->first] && mwDist[it->first] > mwDist[crtNode] + it->second)
			{
				mwDist[it->first] = mwDist[crtNode] + it->second;
				prev[it->first] = crtNode;
				if (inqueue[it->first] == 0)
				{
					inqueue[it->first] = 1;
					que.push(it->first);
				}	
			}
		}
		
		inqueue[crtNode] = 0;
	}
	
	return mwDist[2*n+1] != 0x7fffffff;
}