Pagini recente » Cod sursa (job #1923311) | Cod sursa (job #2038786) | Cod sursa (job #2168282) | Cod sursa (job #24370) | Cod sursa (job #676652)
Cod sursa(job #676652)
#include <fstream>
#include <queue>
#include <cassert>
#include <algorithm>
#include <cmath>
using namespace std;
#define NMAX 900
#define inf 10000000
#define in "adapost.in"
#define out "adapost.out"
double edges[NMAX * NMAX];
double coordX[NMAX],coordY[NMAX],sCoordX[NMAX],sCoordY[NMAX];
double Cost[NMAX][NMAX],dist[NMAX];
int G[NMAX][NMAX],F[NMAX][NMAX],C[NMAX][NMAX];
int inQ[NMAX],t[NMAX],cntInQ[NMAX];
int s,d,N;
double minValue = inf,minFlow = inf,lim;
queue<int> Q;
inline void refresh()
{
int i,j;
for(i = s; i <= d; i++)
for(j = s; j <= d; j++)
F[i][j] = F[j][i] = 0;
}
double min(double a,double b)
{
return (a<b)?a:b;
}
double abs1(double a)
{
return (a>0)?a:-a;
}
inline double bellman_ford(double lim)
{
int nod,v,i;
double flux = inf;
for(i = s; i <= d; i++)
inQ[i] = 0,dist[i] = inf,cntInQ[i] = 0;
dist[s] = 0; inQ[s] = 0; Q.push(s);
while(!Q.empty())
{
nod = Q.front();
Q.pop(), inQ[nod] = 0;
for(i = 1; i <= G[nod][0]; i++)
{
v = G[nod][i];
if((Cost[nod][v] <= lim)&&(dist[v] > dist[nod] + Cost[nod][v]) && C[nod][v] > F[nod][v])
{
dist[v] = dist[nod] + Cost[nod][v];
t[v] = nod;
if(!inQ[v])
if(cntInQ[v] > N)
return inf;
else
cntInQ[v]++,inQ[v] = 1,Q.push(v);
}
}
}
if(dist[d] != inf)
{
for(i = d; i != s; i = t[i])
flux = min(flux,C[t[i]][i] - F[t[i]][i]);
for(i = d; i != s; i = t[i])
{
F[t[i]][i] += flux;
F[i][t[i]] -= flux;
}
return flux * dist[d];
}
return 0;
}
int GetCard()
{
int i,j,card = 0;
double max = 0;
for(i = 2; i <= N + 1; i++)
for(j = N + 2; j < d; j++)
if(F[i][j] == 1)
{
card++;
break;
}
return card;
}
double Flow()
{
int card;
double ans = 0,tans;
do{
tans = bellman_ford(lim);
if(tans == inf)
return inf;
ans += tans;
}while(tans > 0);
card = GetCard();
assert(card <= N);
if(card < N)
return inf;
else
return ans;
}
void solve()
{
int i;
double aux = inf;
for(i = N; aux == inf; i++)
{
lim = edges[i];
aux = Flow();
refresh();
}
minFlow = aux;
minValue = edges[i];
}
double distanta(double x,double y,double x1,double y1)
{
return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
int main()
{
ifstream fin(in);
ofstream fout(out);
fin>>N;
int ind = 0,i,j,p,q;
s = 1;
d = 2 * N + 2;
for(i = 1; i <= N; i++)
fin>>coordX[i]>>coordY[i];
for(i = 1; i <= N; i++)
fin>>sCoordX[i]>>sCoordY[i];
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
{
edges[++ind] = distanta(coordX[i],coordY[i],sCoordX[j],sCoordY[j]);
p = i + 1;
q = j + N + 1;
Cost[p][q] = edges[ind];
Cost[q][p] = -edges[ind];
C[p][q] = 1;
G[p][++G[p][0]] = q;
G[q][++G[q][0]] = p;
}
sort(edges + 1, edges + N * N + 1);
for(i = 2; i <= N + 1; i++)
{
C[s][i] = 1;
G[s][++G[s][0]] = i;
G[i][++G[i][0]] = s;
}
for(i = N + 2; i <= d; i++)
{
G[i][++G[i][0]] = d;
G[d][++G[d][0]] = i;
C[i][d] = 1;
}
solve();
fout<<minValue<<' '<<minFlow<<'\n';
fin.close();
fout.close();
return 0;
}