Pagini recente » Cod sursa (job #1884065) | Cod sursa (job #2833081) | Cod sursa (job #1683581) | Cod sursa (job #2557120) | Cod sursa (job #329700)
Cod sursa(job #329700)
#include <cstdio>
#include <math.h>
#include <vector>
#define maxn 410
#define inf 2000000000
using namespace std;
struct punct {
double x, y;
};
int n, i, j, src, dst, ok;
punct v[2 * maxn];
int dist[2 * maxn][2 * maxn];
int dmax, cmin, cst, flow, rez;
int f[2 * maxn][2 * maxn], c[2 * maxn][2 * maxn];
int ct[2 * maxn], up[2 * maxn], viz[2 * maxn];
int q[maxn * maxn];
vector <int> g[2 * maxn];
inline double distanta(punct a, punct b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init() {
// memset(up, -1, sizeof(up));
memset(viz, 0, sizeof(viz));
for (i = 0; i <= 2 * n + 1; i++)
ct[i] = inf;
}
int bford() {
int p, u;
int nod, fiu, i;
int unit;
p = u = 1;
q[1] = 0; viz[0] = 1; ct[0] = 0;
while (p <= u) {
nod = q[p];
for (i = 0; i < g[nod].size(); i++) {
fiu = g[nod][i];
if (c[nod][fiu] - f[nod][fiu] > 0 && ct[fiu] > ct[nod] + dist[nod][fiu]) {
ct[fiu] = ct[nod] + dist[nod][fiu];
up[fiu] = nod;
if (viz[fiu] == 0) {
viz[fiu] = 1;
u++;
q[u] = fiu;
}
}
}
p++;
}
if (ct[dst] != inf) {
ok = 1;
unit = inf;
for (nod = dst; nod != src; nod = up[nod])
unit = min(unit, c[up[nod]][nod] - f[up[nod]][nod]);
for (nod = dst; nod != src; nod = up[nod]) {
f[up[nod]][nod] += unit;
f[nod][up[nod]] -= unit;
}
flow += unit;
return unit * ct[dst];
}
return 0;
}
bool solve(int d, int &cst) {
//construiesc grafu si fac flux
//toate muchiile existente o sa aiba capacitate 1
for (i = 0; i <= 2 * n + 1; i++)
g[i].clear();
memset(f, 0, sizeof(f));
// memset(c, 0, sizeof(c));
src = 0;
dst = 2 * n + 1;
for (i = 1; i <= n; i++) {
g[src].push_back(i);
dist[src][i] = 0;
c[src][i] = 1;
}
for (i = n + 1; i <= 2 * n; i++) {
g[i].push_back(dst);
c[i][dst] = 1;
dist[i][dst] = 0;
}
for (i = 1; i <= n; i++)
for (j = n + 1; j <= 2 * n; j++)
if (dist[i][j] <= d) {
g[i].push_back(j);
g[j].push_back(i);
dist[j][i] = -dist[i][j];
c[i][j] = 1;
}
ok = 1; rez = 0;
flow = 0;
while (ok) {
ok = 0;
init();
rez += bford();
}
if (flow == n) {
cst = rez;
return true;
}
return false;
}
void bsearch(int left, int right) {
int m;
while (left <= right) {
m = (left + right) / 2;
// fprintf(stderr, "%d\n", m);
if (solve(m, cst)) {
if (m < dmax) {
dmax = m;
cmin = cst;
}
right = m - 1;
}
else
left = m + 1;
}
}
int main() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= 2 * n; i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
for (i = 1; i <= 2 * n; i++)
for (j = 1; j <= 2 * n; j++)
dist[i][j] = (int) (1000 * distanta(v[i], v[j]));
dmax = inf;
bsearch(0, 1000000);
printf("%d %d\n", dmax, cmin);
return 0;
}