Pagini recente » Cod sursa (job #1388987) | Cod sursa (job #1557829) | Cod sursa (job #2438766) | Cod sursa (job #3242826) | Cod sursa (job #1135717)
#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;
}