Pagini recente » Cod sursa (job #1963019) | Cod sursa (job #1124839) | Cod sursa (job #1884570) | Cod sursa (job #2181710) | Cod sursa (job #71053)
Cod sursa(job #71053)
using namespace std;
#include<fstream>
#include<stdio.h>
#include<math.h>
#define Nmax 405
#define inf 100000000.0
int N;
double cxad[Nmax],cyad[Nmax],cxsol[Nmax],cysol[Nmax],dist[Nmax*Nmax],init[Nmax][Nmax];
double cost[2*Nmax][2*Nmax],flux[2*Nmax];
char cap[2*Nmax][2*Nmax];
int q[Nmax*Nmax],ant[Nmax],soldat[2*Nmax];
char inq[2*Nmax];
int vec[Nmax][Nmax],nvec[Nmax];
int x[Nmax*Nmax],y[Nmax*Nmax];
char viz[2*Nmax];
int nv=0;
ifstream fin("adapost.in");
FILE *fout=fopen("adapost.out","w");
double flow(double Vmax)
{
int i,j;
//initializare
for(i=1;i<=N;i++)
{
nvec[i]=0;
for(j=1;j<=N;j++)
{
cap[j+N][i]=0;
if(init[i][j] <= Vmax)
{
vec[i][++nvec[i]]=j+N;
cost[i][j+N]=init[i][j];
cost[j+N][i]=-init[i][j];
cap[i][j+N]=1;
}
else
cap[i][j+N]=0;
}
}
for(i=1;i<=N;i++)
{
cap[0][i]=cap[i+N][2*N+1]=1;
cap[i][0]=cap[2*N+1][i+N]=0;
cost[0][i]=cost[i+N][2*N+1]=0.0;
cost[i][0]=cost[2*N+1][i+N]=0.0;
}
int X,dest=2*N+1,ori=0,li,lf;
double F=0.0;
while(1)
{
for(i=1;i<=2*N+1;i++)
flux[i]=inf;
flux[0]=0.0;
li=1;lf=1;
q[1]=0;
inq[0]=1;
while(li<=lf)
{
X=q[li];
if(X<=N && X>0)
{
for(j=1;j<=nvec[X];j++)
{
i=vec[X][j];
if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
if(!inq[i])
{
q[++lf]=i;
inq[i]=1;
}
}
}
}
else
{
if(X==0)
{
for(i=1;i<=N;i++)
if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
if(!inq[i])
{
q[++lf]=i;
inq[i]=1;
}
}
}
else
{
i=soldat[X];
if(cap[X][i] && flux[i] > flux[X] + cost[X][i] && flux[X] + cost[X][i] <= flux[dest])
{
flux[i]=flux[X]+cost[X][i];
ant[i]=X;
if(!inq[i])
{
q[++lf]=i;
inq[i]=1;
}
}
if(cap[X][dest] && flux[dest]> flux[X] + cost[X][dest])
{
flux[dest]=flux[X]+cost[X][dest];
ant[dest]=X;
}
}
}
li++;
inq[X]=0;
}
if(flux[dest] == inf)
if(ori==N)
return F;
else
return -1.0;
i=dest;
while(i>0)
{
cap[ant[i]][i]=0;
cap[i][ant[i]]=1;
if(i>N && ant[i]<=N)
soldat[i]=ant[i];
i=ant[i];
}
F+=flux[dest];
ori++;
}
}
int main()
{
int i,j,k,auxx;
double dx,dy,val,aux;
fin>>N;
for(i=1;i<=N;i++)
fin>>cxsol[i]>>cysol[i];
for(i=1;i<=N;i++)
fin>>cxad[i]>>cyad[i];
k=0;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
dx=cxsol[i] - cxad[j];
dy=cysol[i] - cyad[j];
init[i][j]= sqrt(dx*dx + dy*dy);
dist[++k]=init[i][j];
x[k]=i;
y[k]=j+N;
}
for(i=1;i<=N*N;i++)
{
j=i;
while(j/2 && dist[j/2] < dist[j])
{
aux=dist[j/2];
dist[j/2]=dist[j];
dist[j]=aux;
auxx=x[j/2];
x[j/2]=x[j];
x[j]=auxx;
auxx=y[j/2];
y[j/2]=y[j];
y[j]=auxx;
j/=2;
}
}
i=N*N;
while(i>1)
{
aux=dist[1];
dist[1]=dist[i];
dist[i]=aux;
auxx=x[1];
x[1]=x[i];
x[i]=auxx;
auxx=y[1];
y[1]=y[i];
y[i]=auxx;
i--;
j=1;
while(1)
{
k=j*2;
if(k>i) break;
if(k+1<=i && dist[k+1] > dist[k]) k++;
if(dist[j] >= dist[k]) break;
aux=dist[j];
dist[j]=dist[k];
dist[k]=aux;
auxx=x[k];
x[k]=x[j];
x[j]=auxx;
auxx=y[k];
y[k]=y[j];
y[j]=auxx;
j=k;
}
}
int li,lf,mij;
double distMin,totalMin,valinit=0;
for(i=1;i<=N*N;i++)
{
if(viz[x[i]]==0)
{
viz[x[i]]=1;
nv++;
}
if(viz[y[i]]==0)
{
viz[y[i]]=1;
nv++;
}
if(nv==2*N) break;
}
/*
while(li<=lf)
{
mij=(li+lf)>>1;
val=flow(dist[mij]);
if( val >= 0.0 )
{
distMin= dist[mij];
totalMin= val;
lf=mij-1;
}
else
li=mij+1;
}
fprintf(fout,"%f %f\n",distMin,totalMin);
*/
val=flow(dist[i]);
while(val<0.0)
{
i++;
val=flow(dist[i]);
}
fprintf(fout,"%f %f\n",dist[i],val);
fin.close();
fclose(fout);
return 0;
}