POJ 1486唯一の二分図は良い問題にマッチします

とても良いテーマです.
注意:
多くの透明な長方形のシートが平面に並べられ、各長方形のシートには数値番号があります.
長方形のシートの境界と番号の座標が表示されます.
一意に決定できる矩形シートのアルファベット番号と数字番号を求める.
二分図の問題に簡単に変換できます.
開始問題の意味がすべて一意に一致しなければならないと勘違いするとマッチングシーケンスが出力され、だめならnoneが出力される.
今の問題は肝心な辺を求めることです...エッジを削除しなくても、特判でいいです.

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

struct RECT
{
 	   int minx,maxx,miny,maxy;
}rect[333];
struct POINT
{
 	   int x,y;
}point[333];
struct EDGE
{
 	   int v,next;
}E[333333];

int Edgenum,ptr[333],match[333],match2[333];
bool vis[333];

bool judge( RECT a, POINT b )
{
 	 if( a.minx<b.x && b.x<a.maxx && a.miny<b.y && b.y<a.maxy )
 	 	 return true;
 	 return false;
}
void addEdge( int u,int v )
{
 	 E[Edgenum].v=v;
 	 E[Edgenum].next=ptr[u];
 	 ptr[u]=Edgenum++;
}

bool Match( int cur,int *array,int xu=0,int xv=0 )
{
 	 for( int i=ptr[cur];i!=-1;i=E[i].next )
 	 {
	  	  if( xu==cur && xv==E[i].v )
	  	  	  continue;
	  	  if( !vis[E[i].v] )
	  	  {
		   	  vis[E[i].v]=true;
		   	  if( array[E[i].v]==-1 || Match(array[E[i].v],array,xu,xv) )
		   	  {
			   	  array[E[i].v]=cur;
			   	  return true;
			  }
   		  }
	 }
	 return false;
}

int main()
{
 	int N;int cases=0;
 	while( scanf("%d",&N)!=EOF,N )
 	{
	 	   memset( match,-1,sizeof(match) );
	 	   memset( ptr,-1,sizeof(ptr) );
	 	   Edgenum=0;
	 	   for( int i=1;i<=N;i++ )
	 	   		scanf( "%d %d %d %d",&rect[i].minx,&rect[i].maxx,&rect[i].miny,&rect[i].maxy );
	 	   for( int i=1;i<=N;i++ )
	 	   		scanf( "%d %d",&point[i].x,&point[i].y );
	 	   for( int i=1;i<=N;i++ )
	 	   for( int j=1;j<=N;j++ )
	 	   		if( judge(rect[i],point[j]) )
	 	   			addEdge(j+N,i);//       match       
	 	   int MaxMatch=0;
	 	   for( int i=N+1;i<=N+N;i++ )
	 	   {
		   		memset( vis,0,sizeof(vis) );
		   		if( Match(i,match) )
		   			MaxMatch++;
		   }
		   printf( "Heap %d
",++cases );
		   if( MaxMatch!=N )
		   {
		   	   printf( "none

" );
		   	   continue;
		   }
		   bool blank=false;
		   //      
		   for( int i=1;i<=N;i++ )
		   {
		   		int NowMatch=0;
		   		memset( match2,-1,sizeof(match2) );
		   		for( int j=N+1;j<=N+N;j++ )
		   		{
				 	 memset( vis,0,sizeof(vis) );
				 	 if( Match( j,match2,match[i],i ) )
				 	 	 NowMatch++;
  	 	 		}
  	 	 		if( NowMatch<MaxMatch )
  	 	 		{
				 	if( blank )
				 		printf( " " );
				 	blank=true;
				 	printf( "(%c,%d)",i+'A'-1,match[i]-N );
  	 	 			//printf( "none

" );
  	 	 			//goto A;
			    }
   		   }
		   if( blank==false )
		   	   printf( "none" );
		   printf( "

" );
  	}
  	return 0;
}