Pagini recente » Cod sursa (job #2010966) | Istoria paginii runda/oji_2020_cls10/clasament | Cod sursa (job #1547847) | Cod sursa (job #906129) | Cod sursa (job #1795963)
#include <bits/stdc++.h>
#define dim 1024
#define x first
#define y second
#define INF 1000000
#define source 0
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
int capacity[1024][1024], flow[1024][1024], N, T[1024], Left[401], Right[401], destination;
double solution, mainSolution, cost[1024][1024], D[1024], stanga = 1000000, dreapta, E[1024][1024];
pair< double, double> soldat[1024], adapost[1024];
bitset<1024>v;
struct cmp {
bool operator()(pair<double, int> a, pair<double, int> b) {
return a.first > b.first;
}
};
priority_queue<pair<double, int>, vector< pair<double, int> >, cmp> H;
vector <int> L[1024];
vector <int> G[1024];
queue <int> Q;
class Comp {
public:
bool operator()(const pair<int, double> &a, const pair<int, double> &b) {
return a.second > b.second;
}
};
priority_queue< pair<int, double>, vector< pair<int, double> >, Comp > heap;
double dist[dim], newDist[dim], dijDist[dim];
queue<int> que;
bool inQue[dim];
void bellmanFord() {
for (int i = source; i <= destination; ++i)
dist[i] = INF, inQue[i] = false;
dist[source] = 0;
queue<int> que;
que.push(source);
while (!que.empty()) {
int curr = que.front();
que.pop();
inQue[curr] = false;
for (int adj : L[curr]) {
if (dist[adj] <= dist[curr] + cost[curr][adj] || capacity[curr][adj] == flow[curr][adj])
continue;
dist[adj] = dist[curr] + cost[curr][adj];
if (inQue[adj])
continue;
inQue[adj] = true;
que.push(adj);
}
}
}
bool dijkstra() {
for (int i = source; i <= destination; ++i)
dijDist[i] = INF, newDist[i] = INF;
dijDist[source] = newDist[source] = 0;
heap.push(make_pair(source, 0));
while (!heap.empty()) {
int curr = heap.top().first;
double cst = heap.top().second;
heap.pop();
if (dijDist[curr] != cst)
continue;
for (int adj : L[curr]) {
if (capacity[curr][adj] == flow[curr][adj])
continue;
double temp = dijDist[curr] + cost[curr][adj] + dist[curr] - dist[adj];
if (temp < dijDist[adj]) {
dijDist[adj] = temp;
newDist[adj] = newDist[curr] + cost[curr][adj];
T[adj] = curr;
heap.push(make_pair(adj, temp));
}
}
}
memcpy(dist, newDist, sizeof dist);
return dist[destination] != INF;
}
inline bool cuplaj(const int &node)
{
v[node] = 1;
for(int i = 0; i < G[node].size(); i ++)
{
if(Right[ G[node][i] ] == 0)
{
Left[ node ] = G[node][i];
Right[ G[node][i] ] = node;
return true;
}
}
for(int i = 0; i < G[node].size(); i ++)
{
if( !v[ Right[ G[node][i] ] ] && cuplaj( Right[ G[node][i] ] ))
{
Left[ node ] = G[node][i];
Right[ G[node][i] ] = node;
return true;
}
}
return false;
}
inline bool verif(const double &maxMuchie)
{
memset(Left, 0, sizeof(Left));
memset(Right, 0, sizeof(Right));
for(int i = 1; i <= N; i ++)
{
G[i].clear();
for(int j = 1; j <= N; j ++)
{
if(cost[i][N + j] - maxMuchie < 0.000001)
{
G[i].push_back(j);
}
}
}
bool ok = true;
int cardCuplaj = 0;
while(ok)
{
ok = false;
v.reset();
for(int i = 1; i <= N; i ++)
{
if(Left[i] == 0 & cuplaj(i))
{
cardCuplaj ++;
ok = true;
}
}
}
return cardCuplaj == N;
}
inline void maxFlow(const double &maxMuchie)
{
for(int i = 0; i <= 801; i ++)
{
L[i].clear();
}
for(int i = 1; i <= N; i ++)
{
L[source].push_back(i);
L[i].push_back(source);
capacity[source][i] = 1;
L[destination].push_back(i + N);
L[i + N].push_back(destination);
capacity[i + N][destination] = 1;
}
for(int i = 1; i <= N; i ++)
{
for(int j = 1; j <= N; j ++)
{
if( cost[i][N + j] - maxMuchie < 0.000001 )
{
L[i].push_back(N + j);
L[N + j].push_back(i);
capacity[i][N + j] = 1;
}
}
}
bellmanFord();
while(dijkstra())
{
int Fmin = INF;
int x = destination;
while(x > source)
{
Fmin = min(Fmin, capacity[ T[x] ][x] - flow[ T[x] ][x]);
x = T[x];
}
x = destination;
while(x > source)
{
flow[ T[x] ][x] += Fmin;
flow[x][ T[x] ] -= Fmin;
x = T[x];
}
solution += dist[destination] * Fmin;
}
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i ++)
{
fin >> soldat[i].x >> soldat[i].y;
}
for(int i = 1; i <= N; i ++)
{
fin >> adapost[i].x >> adapost[i].y;
}
for(int i = 1; i <= N; i ++)
{
for(int j = 1; j <= N; j ++)
{
cost[i][N + j] = sqrt( (adapost[j].y - soldat[i].y) * (adapost[j].y - soldat[i].y) +
(adapost[j].x - soldat[i].x) * (adapost[j].x - soldat[i].x) );
cost[N + j][i] = -cost[i][N + j];
dreapta = max(dreapta, cost[i][N + j]);
}
}
stanga = 0;
destination = 2 * N + 1;
for (int i = 1; i <= 21; i++) {
double middle = (stanga + dreapta) / 2;
if(verif(middle))
dreapta = middle;
else
stanga = middle;
}
maxFlow(dreapta);
fout << setprecision(5) << fixed << dreapta << " " << solution;
return 0;
}