Pagini recente » Cod sursa (job #1554569) | Cod sursa (job #1372733) | Cod sursa (job #1806502) | Cod sursa (job #491229) | Cod sursa (job #1134847)
#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;
}