Pagini recente » Cod sursa (job #232334) | Cod sursa (job #1232224) | Cod sursa (job #1242446) | Cod sursa (job #1525057) | Cod sursa (job #580880)
Cod sursa(job #580880)
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int N = 1000;
bool viz[N], inq[N];
queue <int> Q;
const int INF = 1000000000;
vector <int> L[N];
int sol, S, D, n, dis[N], tata[N], l_pair[N], r_pair[N], flux[N][N], cost[N][N], cap[N][N];
double sx[N], sy[N], bx[N], by[N];
void read() {
freopen("adapost.in", "r", stdin);
freopen("adapost.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%lf %lf", &sx[i], &sy[i]);
for (int j = 1; j <= n; ++ j)
scanf("%lf %lf", &bx[j], &by[j]);
}
double dist(double x1, double y1, double x2, double y2) {
return (double)sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void init() {
S = 0;
D = 2 * n + 1;
for (int i = 1; i <= n; ++ i) {
L[S].push_back(i);
L[i].push_back(S);
cap[S][i] = 1;
}
for (int j = 1; j <= n; ++ j) {
L[n + j].push_back(D);
L[D].push_back(n + j);
cap[n + j][D] = 1;
}
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j) {
L[i].push_back(n + j);
L[n + j].push_back(i);
cost[i][n + j] = dist(sx[i], sy[i], bx[j], by[j]) * 10000;
cost[n + j][i] = - cost[i][n + j];
cap[i][n + j] = 1;
}
}
bool cupleaza(int nod, int val) {
if (viz[nod])
return 0;
viz[nod] = 1;
for (int j = 0; j < L[nod].size(); ++ j)
if (cost[nod][L[nod][j]] <= val && (! r_pair[L[nod][j]]) && L[nod][j] != S) {
l_pair[nod] = L[nod][j];
r_pair[L[nod][j]] = nod;
return 1;
}
for (int j = 0; j < L[nod].size(); ++ j)
if (cost[nod][L[nod][j]] <= val && r_pair[L[nod][j]] && cupleaza(r_pair[L[nod][j]], val) && L[nod][j] != S) {
l_pair[nod] = L[nod][j];
r_pair[L[nod][j]] = nod;
return 1;
}
return 0;
}
void reset() {
for (int i = 0; i < N; ++ i)
viz[i] = 0;
}
void hard_reset() {
for (int i = 0; i < N; ++ i)
l_pair[i] = r_pair[i] = 0;
}
int cuplaj(int val) {
bool ok = true;
int pairs = 0;
hard_reset();
while(ok) {
reset();
ok = false;
for (int i = 1; i <= n; ++ i)
if ((! l_pair[i]) && cupleaza(i, val)) {
++ pairs;
ok = true;
}
}
return pairs;
}
int cautb() {
int i = 0, pas = 1 << 20;
for (i = 0; pas; pas >>= 1)
if (cuplaj(i + pas) < n)
i += pas;
return i + 1;
}
void reset_BF() {
for (int i = 0; i < N; ++ i) {
dis[i] = INF;
inq[i] = 0;
tata[i] = 0;
}
}
bool BF(int val) {
int nodc = 0;
reset_BF();
Q.push(S);
inq[S] = 0;
dis[S] = 0;
while (! Q.empty()) {
nodc = Q.front();
Q.pop();
if (nodc == D)
continue;
for (int j = 0; j < L[nodc].size(); ++ j)
if (cost[nodc][L[nodc][j]] <= val && dis[nodc] + cost[nodc][L[nodc][j]] < dis[L[nodc][j]] && flux[nodc][L[nodc][j]] < cap[nodc][L[nodc][j]]) {
dis[L[nodc][j]] = dis[nodc] + cost[nodc][L[nodc][j]];
tata[L[nodc][j]] = nodc;
if (! inq[L[nodc][j]]) {
Q.push(L[nodc][j]);
inq[L[nodc][j]] = 1;
}
}
}
if (dis[D] != INF) {
int deprop = INF;
for (int i = D; i != S; i = tata[i])
if (cap[tata[i]][i] - flux[tata[i]][i] < deprop)
deprop = cap[tata[i]][i] - flux[tata[i]][i];
for (int i = D; i != S; i = tata[i]) {
flux[tata[i]][i] += deprop;
flux[i][tata[i]] -= deprop;
}
sol += deprop * dis[D];
}
return (dis[D] != INF);
}
int fmcm(int d) {
while (BF(d));
return sol;
}
int main() {
read();
init();
int d = cautb();
printf("%lf ", (double)d / 10000.00);
printf("%lf\n", (double)fmcm(d) / 10000.00);
return 0;
}