Pagini recente » Cod sursa (job #3261775) | Cod sursa (job #3156567) | Cod sursa (job #1884436) | Cod sursa (job #2308734) | Cod sursa (job #2507755)
#include <fstream>
#include <cmath>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
const int NMax = 800, oo = 2e9;
double X[NMax + 5], Y[NMax + 5], Cost[NMax + 5], Dist[NMax + 5][NMax + 5];
int N, TT[NMax + 5], F[NMax + 5][NMax + 5], Sink, Sol, C[NMax + 5][NMax + 5];
bool InQ[NMax + 5];
struct edge{int x, y; double dist;};
vector <int> G[NMax + 5];
queue <int> Q;
vector <edge> E;
double Euclid(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool BellmanFord()
{
for(int i = 0; i <= Sink; i++)
Cost[i] = oo, TT[i] = -1, InQ[i] = false;
Q.push(0), Cost[0] = 0, InQ[0] = true;
while(!Q.empty())
{
int Node = Q.front(); Q.pop(), InQ[Node] = false;
for(int Next : G[Node])
if(F[Node][Next] != C[Node][Next] && Cost[Node] + Dist[Node][Next] < Cost[Next])
{
Cost[Next] = Cost[Node] + Dist[Node][Next];
TT[Next] = Node;
if(InQ[Next] == false)
Q.push(Next), InQ[Next] = true;
}
}
return (Cost[Sink] != oo);
}
double Flow(double DistMax)
{
for(int i = 0; i <= Sink; i++)
{
if(i != 0 && i != Sink)
{
while(G[i].size() && G[i].back() != 0 && G[i].back() != Sink)
G[i].pop_back();
}
for(int j = 0; j <= Sink; j++)
F[i][j] = 0;
}
for(auto Edge : E)
{
if(Edge.dist > DistMax) break;
G[Edge.x].push_back(Edge.y);
G[Edge.y].push_back(Edge.x);
C[Edge.x][Edge.y] = 1;
}
for(int i = 1; i <= N; i++)
if(G[i].empty())
return -1;
double Ans = 0;
int FluxMax = 0;
while(BellmanFord())
{
for(int i = Sink; TT[i] != -1; i = TT[i])
F[TT[i]][i]++, F[i][TT[i]]--;
Ans += Cost[Sink], FluxMax++;
}
return ((FluxMax == N) ? Ans : -1);
}
inline bool compare(edge A, edge B)
{
return A.dist < B.dist;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
fin >> X[i] >> Y[i];
for(int i = N + 1; i <= 2 * N; i++)
{
double x, y;
fin >> x >> y;
for(int soldier = 1; soldier <= N; soldier++)
{
Dist[soldier][i] = Euclid(x, y, X[soldier], Y[soldier]);
Dist[i][soldier] = -Dist[soldier][i];
E.push_back({soldier, i, Dist[soldier][i]});
}
}
sort(E.begin(), E.end(), compare);
Sink = 2 * N + 1;
for(int i = 1; i <= N; i++)
G[0].push_back(i), G[i].push_back(0), C[0][i] = 1;
for(int i = N + 1; i <= 2 * N; i++)
G[i].push_back(Sink), G[Sink].push_back(i), C[i][Sink] = 1;
for(int step = (1 << 21); step > 0; step >>= 1)
{
if(Flow((Sol + step) / 1000.0) == -1)
Sol += step;
}
fout << fixed << setprecision(3) << (Sol + 1) / 1000.0 << " " << Flow((Sol + 1) / 1000.0) << '\n';
fin.close();
fout.close();
return 0;
}