Pagini recente » Cod sursa (job #1026797) | Cod sursa (job #1550855) | Cod sursa (job #3227883) | Cod sursa (job #1324196) | Cod sursa (job #1760639)
#include <bits/stdc++.h>
#define x first
#define y second
#define INF 1000000
using namespace std;
ifstream fin("adapost.in");
ofstream fout("adapost.out");
int capacity[1024][1024], F[1024][1024], N, T[1024], flux;
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;
bool BF(double maxMuchie)
{
for(int i = 0; i <= 2 * N; i ++)
{
D[i] = INF;
v[i] = 0;
}
D[0] = 0;
D[808] = INF;
v[808] = 0;
Q.push(0);
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( ( capacity[node][neighbour] > F[node][neighbour] ) && (cost[node][neighbour] <= maxMuchie) )
{
D[neighbour] = D[node] + cost[node][neighbour];
T[neighbour] = node;
if(v[neighbour] == 0)
{
Q.push(neighbour);
v[neighbour] = 1;
}
}
}
}
return D[808] != INF ? true : false;
}
bool cuplaj( double maxMuchie)
{
solution = 0;
flux = 0;
while( BF(maxMuchie) )
{
int x = 808;
int minFlux = INF;
while(x != 0)
{
minFlux = min( minFlux, capacity[ T[x] ][x] - F[ T[x] ][x] );
x = T[x];
}
x = 808;
while(x != 0)
{
solution += minFlux * cost[ T[x] ][x];
F[ T[x] ][x] += minFlux;
F[x][ T[x] ] -= minFlux;
x = T[x];
}
flux += minFlux;
}
memset(F, 0, sizeof(F));
return solution != 0 && flux == N ? true : false;
}
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 ++)
{
L[0].push_back(i);
L[i].push_back(0);
capacity[0][i] = 1;
L[808].push_back(N + i);
L[N + i].push_back(808);
capacity[N + i][808] = 1;
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 > dreapta)
{
dreapta = dist;
}
if(dist < stanga)
{
stanga = dist;
}
L[i].push_back(N + j);
capacity[i][N + j] = 1;
cost[i][N + j] = dist;
cost[N + j][i] = -dist;
}
}
while(stanga <= dreapta)
{
double middle = (stanga + dreapta) / 2;
if(cuplaj(middle))
{
dreapta = middle - 0.0001;
mainSolution = solution;
}
else
{
stanga = middle + 0.0001;
}
}
fout << dreapta << " " << mainSolution;
return 0;
}