Pagini recente » Monitorul de evaluare | Cod sursa (job #472073) | Cod sursa (job #2579919) | Cod sursa (job #2227404) | Cod sursa (job #1795835)
#include <bits/stdc++.h>
#define x first
#define y second
#define INF 1000000
#define source 0
#define destination 801
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
int capacity[1024][1024], flow[1024][1024], N, T[1024], Left[1024], Right[1024];
double solution, mainSolution, cost[1024][1024], D[1024], stanga = 1000000, dreapta;
pair< double, double> soldat[1024], adapost[1024];
bitset<1024>v;
vector <int> L[1024];
queue <int> Q;
inline bool cuplaj(const int &node)
{
v[node] = 1;
for(int i = 0; i < L[node].size(); i ++)
{
if(Right[ L[node][i] ] == 0)
{
Left[ node ] = L[node][i];
Right[ L[node][i] ] = node;
return true;
}
}
for(int i = 0; i < L[node].size(); i ++)
{
if( !v[ Right[ L[node][i] ] ] && cuplaj( Right[ L[node][i] ] ))
{
Left[ node ] = L[node][i];
Right[ L[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 ++)
{
L[i].clear();
}
for(int i = 1; i <= N; i ++)
{
for(int j = 1; j <= N; j ++)
{
double dist = 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) );
if(dist - maxMuchie < 0.000001)
{
L[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 bool bellmanFord()
{
for(int i = 1; i <= 801; i ++)
{
D[i] = INF;
v[i] = 0;
}
D[source] = 0;
Q.push(source);
while(!Q.empty())
{
int node = Q.front();
v[node] = 0;
Q.pop();
for(int i = 0; i < L[node].size(); i ++)
{
int neighbour = L[node][i];
if(D[neighbour] > D[node] + cost[node][neighbour] && capacity[node][neighbour] > flow[node][neighbour])
{
D[neighbour] = D[node] + cost[node][neighbour];
T[neighbour] = node;
if(v[neighbour] == 0)
{
v[neighbour] = 1;
Q.push(neighbour);
}
}
}
}
return D[destination] != INF;
}
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 ++)
{
double dist = 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) );
if( dist - maxMuchie < 0.000001 )
{
L[i].push_back(N + j);
L[N + j].push_back(i);
cost[i][N + j] = dist;
cost[N + j][i] = -dist;
capacity[i][N + j] = 1;
}
}
}
while(bellmanFord())
{
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 += D[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;
}
stanga = 0; dreapta = 1415;
for (int i = 1; i <= 22; i++) {
double middle = (stanga + dreapta) / 2;
if(verif(middle))
dreapta = middle;
else
stanga = middle;
}
maxFlow(dreapta);
fout << setprecision(5) << fixed << dreapta << " " << solution;
return 0;
}