Cod sursa(job #1134847)

Utilizator eukristianCristian L. eukristian Data 6 martie 2014 22:36:16
Problema Adapost Scor 45
Compilator c Status done
Runda Arhiva de probleme Marime 5.41 kb
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <stdlib.h>
#include <string.h>

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

int n;

struct coord { double x, y; } soldiers[MAXN], shelters[MAXN];
struct node {
	int key;
	double weight;
	struct node *next;
};

struct node *gr[MAXN];
double distances[160001];

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));
}
int compar (const void* p1, const void* p2)
{
	
	if (*((double*)p1) == *((double*)p2))
		return 0;
	if (*((double*)p1) < *((double*)p2))
		return -1;
	return 1;
}

inline double abso(double x)
{
	return x < 0.0 ? -x : x;
}
/* Hopcroft Karp Matching - procedures and data : */
int pair[MAXN];
int dist[MAXN];
int queue[10*MAXN];

int hopcroftKarpMatch(double maxWeight);
char hkBFS(double maxWeight);
char hkDFS(int nd, double maxWeight);

/* 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(double maxWeight);
char bellman(double maxWeight);

/* END OF Minimum weight max matching */

double binSearchWeight(int left, int right);

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;
			struct node *q = (struct node*) malloc(sizeof(struct node));
			q->key = j + n;
			q->weight = dst;
			q->next = gr[i];
			gr[i] = q; 
			
			q = (struct node*) malloc(sizeof(struct node));
			q->key = i;
			q->weight = -dst;
			q->next = gr[j + n];
			gr[j + n ] = q;
			
			
			distances[(i - 1) * n + j] = dst;
			capacity[i][j + n] = 1;
		}
		
		if (lmin > gmax)
			gmax = lmin;
	}
	
	qsort(distances + 1, n * n, sizeof(double), compar);
	int left = 1, right = n * n;
	while (left < right)
	{
		int mid = (left + right) >> 1;
		if (distances[mid] < gmax)
			left = mid + 1;
		else
			right = mid;
	}
	
	right = n*n;
	
	double maxWeight = binSearchWeight(left, right);	
	
	printf("%.5lf %.5lf\n", maxWeight, sumMatch(maxWeight));
	
	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;
		if (hopcroftKarpMatch(distances[mid]) < n)
			left = mid + 1;
		else
			right = mid;
	}
	
	return distances[right];
}

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

char hkBFS(double maxWeight)
{
	int i, ql = 0, qr = -1;
	memset(dist, 0x7f, 2 * (n + 1) * sizeof(int));
	for (i = 1 ; i <= n ; ++i)
		if (pair[i] == 0)
			queue[++qr] = i, dist[i] = 0;
			
	while (ql <= qr)
	{
		int crtNode = queue[ql++];
		if (dist[crtNode] < dist[0])
		{
			struct node *q = gr[crtNode];
		
			while (q != NULL)
			{
				if (q->weight <= maxWeight && dist[pair[q->key]] == 0x7f7f7f7f)
				{
					dist[pair[q->key]] = dist[crtNode] + 1;
					queue[++qr] = pair[q->key];
				} 
				q = q->next;
			}
		}
	}
	
	if (dist[0] != 0x7f7f7f7f)
		return 1;
	return 0;
}

char hkDFS(int nd, double maxWeight)
{
	if (nd == 0)
		return 1;
	struct node *q = gr[nd];
	while (q)
	{
		if (q->weight <= maxWeight && dist[pair[q->key]] == dist[nd] + 1 && hkDFS(pair[q->key], maxWeight) == 1)
		{
			pair[nd] = q->key;
			pair[q->key] = nd;
			return 1;
		}
		q = q->next;
	}
	dist[nd] = 0x7f7f7f7f;
	return 0;
}

/*HK implementation end */


double sumMatch(double maxWeight)
{
	int i;
	double total = 0;
	for (i = 1 ; i <= n ; ++i)
	{
		struct node *q = (struct node *) malloc(sizeof(struct node));
		q->key = i;
		q->weight = 0;
		q->next = gr[0];
		gr[0] = q;
		
		q = (struct node *) malloc(sizeof(struct node));
		q->key = 0;
		q->weight = 0;
		q->next = gr[i];
		gr[i] = q;
		
		q = (struct node *) malloc(sizeof(struct node));
		q->key = n + i;
		q->weight = 0;
		q->next = gr[2*n + 1];
		gr[2*n + 1 ] = q;
		
		q = (struct node *) malloc(sizeof(struct node));
		q->key = 2*n + 1;
		q->weight = 0;
		q->next = gr[n + i];
		gr[n + i] = q;
		
		capacity[0][i] = 1;
		capacity[i + n][2*n+1] = 1;
	}
	
	while (bellman(maxWeight))
	{
		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(double maxWeight)
{
	int i, ql = 0, qr = -1;
	for (i = 0 ; i <= 2 * n + 1;  ++i) 
	{
		mwDist[i] = 0x7fffffff;
		inqueue[i] = 0;
		prev[i] = -1;
	}
	
	mwDist[0] = 0; inqueue[0] = 1; queue[++qr] = 0;
	
	while (ql <= qr)
	{
		int crtNode = queue[ql++];
		struct node* q = gr[crtNode];
		while (q)
		{
			if (abso(q->weight) <= maxWeight && flow[crtNode][q->key] < capacity[crtNode][q->key] && mwDist[q->key] > mwDist[crtNode] + q->weight)
			{
				mwDist[q->key] = mwDist[crtNode] + q->weight;
				prev[q->key] = crtNode;
				if (inqueue[q->key] == 0)
				{
					inqueue[q->key] = 1; 
					queue[++qr] = q->key;
				}
			}
			q = q->next;
		}
		inqueue[crtNode] = 0;
	}
	
	return mwDist[2*n+1] != 0x7fffffff;
}