Pagini recente » Cod sursa (job #659670) | Cod sursa (job #1169032) | Cod sursa (job #2152829) | Cod sursa (job #2415887) | Cod sursa (job #2377084)
#include <bits/stdc++.h>
#define NMAX 810
#define SMAX 405
#define INF 1e9
using namespace std;
unsigned long n,m,S,D, p[NMAX];
vector<pair<double, double>> adapost, soldat;
vector<pair<double, pair<int, int>>> distante;
int ll[SMAX], lr[SMAX];
bitset<SMAX> viz;
vector<int> G[SMAX];
vector<unsigned long> V[NMAX];
int C[NMAX][NMAX], F[NMAX][NMAX];
double Cost[NMAX][NMAX], oldDist[NMAX], result;
inline double sqr(double x)
{
return x*x;
}
bool cupleaza(int nod)
{
if (viz[nod])
return false;
viz[nod] = 1;
for (int vec : G[nod])
if (!lr[vec] || cupleaza(lr[vec]))
{
ll[nod] = vec;
lr[vec] = nod;
return true;
}
for(int nd : G[nod])
if(cupleaza(lr[nd]))
{
ll[nod]=nd;
lr[nd]=nod;
return true;
}
return false;
}
bool cuplaj(unsigned long poz)
{
memset(ll, 0, sizeof(ll));
memset(lr, 0, sizeof(lr));
unsigned long nods = 0;
bool found;
for (unsigned long i = 0; i <= poz; ++i)
G[distante[i].second.first].push_back(distante[i].second.second);
do
{
found = false;
viz.reset();
for (unsigned long i = 1; i <= n; ++i)
if (!ll[i])
if (cupleaza(i))
{
++nods;
found = true;
}
}
while (found);
for (unsigned long i = 1; i <= n; ++i)
G[i].resize(0);
return (nods == n);
}
void belmanFord()
{
for (unsigned long i = 0; i <= D; ++i)
oldDist[i] = INF;
oldDist[S] = 0;
queue<unsigned long> Q;
bitset<NMAX> inQ;
inQ.reset();
for (Q.push(S), inQ[S] = 1; !Q.empty();)
{
unsigned long nod = Q.front();
Q.pop();
inQ[nod] = 0;
for (unsigned long vec : V[nod])
if (C[nod][vec] > 0)
{
double d = oldDist[nod] + Cost[nod][vec];
if (oldDist[vec] > d)
{
oldDist[vec] = d;
if (!inQ[vec])
{
Q.push(vec);
inQ[vec]=1;
}
}
}
}
}
bool dijkastra()
{
priority_queue<pair<double, unsigned long>, vector<pair<double, unsigned long>>, greater<pair<double, unsigned long>>> H;
memset(p, 0, sizeof(p));
double cDist[NMAX], realDist[NMAX];
for (unsigned long i = S; i <= D; ++i)
cDist[i] = INF;
cDist[S] = realDist[S] = 0;
H.push({0, S});
while (!H.empty())
{
double d = H.top().first;
unsigned long nod = H.top().second;
H.pop();
if (cDist[nod] != d)
continue;
for (unsigned long vec : V[nod])
{
if (C[nod][vec] > F[nod][vec])
{
double dst = d + Cost[nod][vec] + oldDist[nod] - oldDist[vec];
if (dst < cDist[vec])
{
cDist[vec] = dst;
realDist[vec] = realDist[nod] + Cost[nod][vec];
p[vec] = nod;
H.push({dst, vec});
}
}
}
}
if (p[D] == 0)
return false;
memcpy(oldDist, realDist, sizeof(oldDist));
int flow = INT_MAX;
for(unsigned long nod = D; nod != S; nod = p[nod])
flow = min(flow, C[p[nod]][nod]-F[p[nod]][nod]);
for (unsigned long nod = D; nod != S; nod = p[nod])
{
F[p[nod]][nod] += flow;
F[nod][p[nod]] -= flow;
}
result += flow * realDist[D];
return true;
}
int main()
{
ifstream fin("adapost.in");
fin >> n;
double x, y;
for (unsigned long i = 0; i < n; ++i)
{
fin >> x >> y;
soldat.push_back({x,y});
}
for (unsigned long i = 0; i < n; ++i)
{
fin >> x >> y;
adapost.push_back({x,y});
}
fin.close();
for (unsigned long i = 0; i < n; ++i)
for (unsigned long j = 0; j < n; ++j)
{
double d = sqrt(sqr(soldat[i].first - adapost[j].first) + sqr(soldat[i].second - adapost[j].second));
distante.push_back({d, {i, j}});
}
sort(distante.begin(), distante.end());
unsigned long st = 0, dr = distante.size()-1;
while (st < dr)
{
unsigned long mij = (st+dr)/2;
if (cuplaj(mij))
{
m = mij;
dr = mij;
}
else st = mij+1;
}
S = 1;
D = 2*n+2;
for (unsigned long i = 2; i <= n+1; ++i)
{
V[S].push_back(i);
V[i].push_back(S);
C[S][i] = 1;
}
for (unsigned long i = n+2; i <= D; ++i)
{
V[D].push_back(i);
V[i].push_back(D);
C[i][D] = 1;
}
for (unsigned long i = 0; i <= m; ++i)
{
unsigned long xx = distante[i].second.first+2;
unsigned long yy = distante[i].second.second+n+2;
C[xx][yy] = 1;
Cost[xx][yy] = distante[i].first;
Cost[yy][xx] = -distante[i].first;
V[xx].push_back(yy);
V[yy].push_back(xx);
}
belmanFord();
for(;dijkastra(););
ofstream fout("adapost.out");
fout << fixed << setprecision(5) << distante[m].first << " " << result;
fout.close();
return 0;
}