Pagini recente » Cod sursa (job #1998853) | Cod sursa (job #3281814) | Cod sursa (job #1010674) | Cod sursa (job #884808) | Cod sursa (job #41531)
Cod sursa(job #41531)
#include <iostream.h>
#include<stdio.h>
typedef struct cutie {long x,y,z;} CUTIE;
typedef struct marcaj {int p; char m;} MARCAJ;
int C[1010][1010],F[1010][1010];
int n,n1,x,y,cap,i,j,f;
int VIZ[1010],LISTA[1010],p,u;
MARCAJ W[1010];
CUTIE BOX[1010];
int min(int, int);
void flux();
void aranjeaza(CUTIE &C)
{
long sir[3],aux;
int i,j;
sir[0]=C.x;
sir[1]=C.y;
sir[2]=C.z;
for (i=0;i<=1;i++)
for (j=i+1;j<=2;j++)
if (sir[i]>sir[j])
{
aux=sir[i];
sir[i]=sir[j];
sir[j]=aux;
}
C.x=sir[0];
C.y=sir[1];
C.z=sir[2];
}
int incape(CUTIE C1,CUTIE C2)
{
if (C1.x<C2.x && C1.y<C2.y && C1.z<C2.z)
return 1;
return 0;
}
int main()
{
// 1 este sursa
// n este destinatia
freopen("cutii.in","r",stdin);
freopen("cutii.out","w",stdout);
cin>>n1;
n=2*n1+2;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
C[i][j]=F[i][j]=0;
for (i=1;i<=n1;i++)
{
cin>>BOX[i].x>>BOX[i].y>>BOX[i].z;
aranjeaza(BOX[i]);
}
for (i=1;i<=n1;i++)
for (j=1;j<=n1;j++)
if (incape(BOX[i],BOX[j])==1)
C[i+1][j+n1+1]=1;
for (i=1;i<=n1;i++)
C[1][i+1]=C[i+n1+1][2*n1+2]=1;
flux();
for (i=2;i<=n1+1;i++)
f+=F[1][i];
cout<<n1-f;
return 0;
}
int min(int a, int b)
{
if (a<=b)
return a;
return b;
}
void flux()
{
int i,eps1,eps2,eps;
while (1)
{
for (i=1;i<=n;i++)
{
VIZ[i]=0;
W[i].m=' ';
W[i].p=0;
}
W[1].m='+';
VIZ[1]=1;
LISTA[1]=1;
p=u=1;
while (p<=u)
{
for(i=1;i<=n;i++)
if (VIZ[i]==0)
if (C[LISTA[p]][i]>0)
if (F[LISTA[p]][i]<C[LISTA[p]][i])
{
u++;
LISTA[u]=i;
VIZ[i]=1;
W[i].p=LISTA[p]; // error!
W[i].m='+';
}
else
;
else
if (C[i][LISTA[p]]>0)
if (F[i][LISTA[p]]>0)
{
u++;
LISTA[u]=i;
VIZ[i]=1;
W[i].p=LISTA[p]; // error!
W[i].m='-';
}
p++;
}
if (W[n].m==' ')
return;
// imbunatatire flux pe lantul nesaturat
eps1=10000;
for (i=n;W[i].p!=0;i=W[i].p)
if (W[i].m=='+')
eps1=min(eps1,C[W[i].p][i]-F[W[i].p][i]);
eps2=10000;
for (i=n;W[i].p!=0;i=W[i].p)
if (W[i].m=='-')
eps2=min(eps2,F[i][W[i].p]); // error!
eps=min(eps1,eps2);
for (i=n;W[i].p!=0;i=W[i].p)
if (W[i].m=='+')
F[W[i].p][i]+=eps;
else
if (W[i].m=='-')
F[i][W[i].p]-=eps; // error!
}
}