최소 경로 덮어쓰기

Dolls
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 19, Accepted users: 16
Problem 12499 : No special judgement
Problem description
Do you remember the box of Matryoshka dolls last week? Adam just got another box of dolls from Matryona. This time, the dolls have different shapes and sizes: some are skinny, some are fat, and some look as though they were attened. Specifically, doll i can be represented by three numbers wi, li, and hi, denoting its width, length, and height. Doll i can fit inside another doll j if and only if wi < wj , li < lj , and hi < hj . That is, the dolls cannot be rotated when fitting one inside another. Of course, each doll may contain at most one doll right inside it. Your goal is to fit dolls inside each other so that you minimize the number of outermost dolls.
Input
The input consists of multiple test cases. Each test case begins with a line with a single integer N, 1 ≤ N ≤ 500, denoting the number of Matryoshka dolls. Then follow N lines, each with three space-separated integers wi, li, and hi (1 ≤ wi; li; hi ≤ 10,000) denoting the size of the ith doll. Input is followed by a single line with N = 0, which should not be processed.
Output
For each test case, print out a single line with an integer denoting the minimum number of outermost dolls that can be obtained by optimally nesting the given dolls.
Sample Input

3
5 4 8
27 10 10
100 32 523
3
1 2 1
2 1 1
1 1 2
4
1 1 1
2 3 2
3 2 2
4 4 4
0

Sample Output

1
3
2

구도할 때 최소한의 경로로 모든 상자를 포함한다는 것을 깨달았다.
나는 탐욕스러운 방법을 사용했고 정방향과 역방향 인접표를 추가했다.
매번 욕심이 가장 많은 상자를 끼워 넣고 이 경로에 있는 상자 노드를 모두 꺼내서 상자 수++로 순환합니다.
상자가 없을 때까지.
이것은 확실히 내가 쓴 비교적 복잡한 절차이다내가 할 수 있는 물건을 다 쓸 뻔했다.아쉽게도 RE가...

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

struct node
{
 	   int x,y,z;
}rec[555];

struct Edge
{
 	   int v,next;
}edge[2222];
int ptr[555],cnt[555],rptr[555];
int top[555],out[555];
int edgenum;

bool judge( node a,node b )
{
 	 if( a.x<b.x && a.y<b.y && a.z<b.z ) return true;
 	 if( a.y<b.x && a.x<b.y && a.z<b.z ) return true;
 	 if( a.x<b.x && a.z<b.y && a.x<b.z ) return true;
 	 if( a.z<b.x && a.x<b.y && a.y<b.z ) return true;
 	 if( a.z<b.x && a.y<b.y && a.x<b.z ) return true;
 	 if( a.y<b.x && a.z<b.y && a.x<b.z ) return true;
 	 return false;
}

void addEdge( int u,int v )
{
 	 edge[edgenum].v=v;
 	 edge[edgenum].next=ptr[u];
 	 ptr[u]=edgenum++;
 	 
 	 edge[edgenum].v=u;
 	 edge[edgenum].next=rptr[v];
 	 rptr[v]=edgenum++;
}


int main()
{
 	int N;
 	while( scanf("%d",&N)!=EOF,N )
 	{
	 	   edgenum=0;
	 	   memset( ptr,-1,sizeof(ptr) );
	 	   memset( rptr,-1,sizeof(rptr) );
	 	   memset( out,0,sizeof(out) );
	 	   for( int i=0;i<N;i++ )
		   	   	scanf( "%d %d %d",&rec[i].x,&rec[i].y,&rec[i].z );
  		   int ans=0;
		   for( int i=0;i<N;i++ )
  		  	    for( int j=0;j<N;j++ )
  		  	    {
			   		 if( judge(rec[i],rec[j]) )
					 	 addEdge( i,j );
   			   }
   		   queue<int> queue;
   		   int outnum=0;
	 	   while( outnum!=N )
	 	   {
		   		  memset( top,0,sizeof(top) );
		   		  memset( cnt,0,sizeof(cnt) );
		   		  while( !queue.empty() ) queue.pop();
		   		  for( int i=0;i<N;i++ )
		   		  {
				   	   if( out[i]==false )
				   	   {
		   		  	   	   for( int j=ptr[i];j!=-1;j=edge[j].next )
		   		  	   	   		if( out[edge[j].v]==false )
		   		  	   				top[edge[j].v]++;
					   }
				  }
		   		  for( int i=0;i<N;i++ )
		   		  	   if( top[i]==0&&out[i]==false )
		   		  	   	   queue.push(i);
		   		  int cur;
		   		  while( !queue.empty() )
		   		  {
				   		 cur=queue.front();
				   		 queue.pop();
				   		 for( int i=ptr[cur];i!=-1;i=edge[i].next )
				   		 {
						  	  if( out[edge[i].v]==false )
						  	  {
				   		 	   	  top[edge[i].v]--;
				   		 	  	  cnt[edge[i].v]=max( cnt[cur]+1,cnt[edge[i].v] );
				   		 	  	  if( top[edge[i].v]==0 )
				   		 	  	  	  queue.push(edge[i].v);
							  }
				         }
   		 		  }
   		 		  out[cur]=true;
  				  outnum++;
   		 		  A:
   		 		  for( int i=rptr[cur];i!=-1;i=edge[i].next )
	   		 	  	   if( cnt[edge[i].v]+1==cnt[cur]&& out[edge[i].v]==false )
	   		 	  	   {
					   	   out[edge[i].v]=true;
 				  		   outnum++;
				  	   	   cur=edge[i].v;
				  	   	   goto A;
				  	   }
				  ans++;
  		   }
   		   printf( "%d
",ans );
  	}
 	return 0;
}

나중에 인터넷에서 문제풀이를 찾아보니 이분도 문제였어요?
왜 그런지 도무지..인터넷에서는 최소 정점 덮어쓰기라고도 한다.
사실 오늘 이분도의 일부 개념을 다시 한 번 복습하여 최소 경로가 덮어씌워진 것이 확실하다.
그리고 최소 경로가 덮어쓰는 그림이 반드시 이분도가 아니라 Vnum-Maxmatch라는 공식으로 표현할 수 있을 뿐이다.
착실하게 2점도 공부!
다음은 AC 코드입니다.

#include<iostream>
using namespace std;

struct EDGE
{
 	   int v,next;
}E[555555];

struct RECT
{
 	   int x,y,z;
}rect[555];

int Edgenum,ptr[1111];

void addEdge( int u, int v )
{
 	 E[Edgenum].v=v;
 	 E[Edgenum].next=ptr[u];
 	 ptr[u]=Edgenum++;
}

bool judge( RECT a,RECT b )
{
 	 if( a.x<b.x && a.y<b.y && a.z<b.z ) return true;
 	 return false;
}

bool vis[1111];
int match[1111];

bool Match( int cur )
{
 	 for( int i=ptr[cur];i!=-1;i=E[i].next )
 	 {
	  	  if( !vis[E[i].v] )
	  	  {
		   	  vis[E[i].v]=true;
		   	  if( match[E[i].v]==-1 || Match( match[E[i].v] ) )
		   	  {
			   	  match[E[i].v]=cur;
			   	  return true;
			  }
   		  }
	 }
	 return false;
}

int main()
{
 	int N;
 	while( scanf("%d",&N)!=EOF,N )
 	{
	 	   memset( ptr,-1,sizeof(ptr) );
	 	   memset( match,-1,sizeof(match) );
	 	   Edgenum=0;
	 	   for( int i=0;i<N;i++ )
	 	   		scanf( "%d %d %d",&rect[i].x,&rect[i].y,&rect[i].z );
	 	   for( int i=0;i<N;i++ )
	 	   for( int j=0;j<N;j++ )
	 	   		if( judge(rect[i],rect[j]) )
	 	   		{
	 	   			addEdge( i,j );
	 	   			//addEdge( j<<1|1,j<<1 );
				}
		   int ans=0;
	 	   for( int i=0;i<N;i++ )
	 	   {
		   		memset( vis,0,sizeof(vis) );
		   		if( Match(i) )
		   			ans++;
		   }
	 	   printf( "%d
",N-ans );
  	}
 	return 0;
}