Cod sursa(job #41531)

Utilizator yo_myhMihut Bogdan-Adrian yo_myh Data 28 martie 2007 12:43:49
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#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!
	}
}