一道很好的题目。
大意：
很多透明的矩形薄片平摊在平面上，每个矩形薄片有数字编号。
现在给出矩形薄片的边界与编号的坐标。
求出能唯一确定的矩形薄片的字母标号与数字编号。
很容易转化成二分图的题。
开始题意弄错以为是必须全部都唯一匹配则输出匹配序，不行则输出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\n",++cases );if( MaxMatch!=N ){printf( "none\n\n" );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\n\n" );//goto A;}}if( blank==false )printf( "none" );printf( "\n\n" );}return 0;
}