Pagini recente » Cod sursa (job #725828) | Cod sursa (job #1638150) | Cod sursa (job #1359175) | Cod sursa (job #221412) | Cod sursa (job #1207294)
#include <algorithm>
#include <bitset>
#include <fstream>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
const int Nmax = 805, INF = 0x3f3f3f3f;
const int Source = 0, Destination = 803;
class Point {
public:
double x, y;
Point(const double _x = 0, const double _y = 0):
x(_x),
y(_y) {}
};
class Edge {
public:
int from, to;
double cost;
Edge(const int _from = 0, const int _to = 0, const double _cost = 0):
from(_from),
to(_to),
cost(_cost) {}
bool operator<(const Edge &e) const {
return cost < e.cost;
}
};
Point Points[Nmax];
int N, Ans;
void Read()
{
ifstream fin("adapost.in");
fin >> N;
for (int i = 1; i <= 2 * N; i++)
fin >> Points[i].x >> Points[i].y;
fin.close();
}
double Dist(const Point a, const Point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
Edge Edges[Nmax * Nmax];
vector<int> G[Nmax];
int L[Nmax], R[Nmax];
bitset<Nmax> V;
void BuildMatchingNetwork(const int T)
{
for (int i = 1; i <= N; i++) G[i].clear();
for (int i = 1; i <= T; i++)
{
G[Edges[i].from].push_back(Edges[i].to - N);
}
memset(L, 0, sizeof(L));
memset(R, 0, sizeof(R));
}
int PairUp(const int node)
{
if (V[node]) return 0;
V[node] = 1;
for (const int p: G[node])
{
if (!R[p])
{
L[node] = p;
R[p] = node;
return 1;
}
}
for (const int p: G[node])
{
if (PairUp(R[p]))
{
L[node] = p;
R[p] = node;
return 1;
}
}
return 0;
}
int GetMatching()
{
for (int ok = 1; ok; )
{
ok = 0;
V.reset();
for (int i = 1; i <= N; i++)
if (!L[i])
ok |=PairUp(i);
}
int ret = 0;
for (int i = 1; i <= N; i++)
if (L[i])
ret++;
return ret;
}
int C[Nmax][Nmax], F[Nmax][Nmax];
int Father[Nmax];
double Cost[Nmax][Nmax], Distt[Nmax];
bitset<Nmax> inQueue;
void AddEdge(const int from, const int to, const int cap, const double cost)
{
G[from].push_back(to);
C[from][to] = cap;
Cost[from][to] = cost;
G[to].push_back(from);
Cost[to][from] = -cost;
}
void BuildFlowNetwork(const int T)
{
for (int i = 1; i <= 2 * N; i++) G[i].clear();
for (int i = 1; i <= T; i++)
AddEdge(Edges[i].from, Edges[i].to, 1, sqrt(Edges[i].cost));
for (int i = 1; i <= N; i++)
{
AddEdge(Source, i, 1, 0);
AddEdge(N + i, Destination, 1, 0);
}
}
bool BellmanFord()
{
queue<int> Q;
for (int i = 1; i <= 2 * N; i++)
Distt[i] = INF;
Distt[Destination] = INF;
inQueue.reset();
for (Q.push(Source); !Q.empty(); )
{
const int node = Q.front();
Q.pop();
inQueue[node] = 0;
for (const int p: G[node])
{
if (C[node][p] == F[node][p]) continue;
if (Distt[p] > Distt[node] + Cost[node][p])
{
Distt[p] = Distt[node] + Cost[node][p];
Father[p] = node;
if (!inQueue[p])
{
inQueue[p] = 1;
Q.push(p);
}
}
}
}
if (Distt[Destination] < INF) return true;
return false;
}
pair<int, double> GetFlow()
{
int flow = 0;
double flowcost = 0;
while (BellmanFord())
{
int fmin = INF;
for (int i = Destination; i != Source; i = Father[i])
fmin = min(fmin, C[Father[i]][i] - F[Father[i]][i]);
for (int i = Destination; i != Source; i = Father[i])
{
F[Father[i]][i] += fmin;
F[i][Father[i]] -= fmin;
}
flow += fmin;
flowcost += fmin * Distt[Destination];
}
return make_pair(flow, flowcost);
}
void Solve()
{
int k = 0;
for (int i = 1; i <= N; i++)
for (int j = N + 1; j <= 2 * N; j++)
Edges[++k] = Edge(i, j, Dist(Points[i], Points[j]));
sort(Edges + 1, Edges + k + 1);
int l = 1, r = k;
while (l <= r)
{
int mid = (l + r) / 2;
BuildMatchingNetwork(mid);
int P = GetMatching();
if (P < N) l = mid + 1;
else
{
Ans = mid;
r = mid - 1;
}
}
}
void Write()
{
ofstream fout("adapost.out");
BuildFlowNetwork(Ans);
pair<int, double> P = GetFlow();
fout << setprecision(5) << fixed;
fout << sqrt(Edges[Ans].cost) << " " << P.second << "\n";
fout.close();
}
int main()
{
Read();
Solve();
Write();
}