题目链接：
POJ 1486 Sorting Slides
题意：
有n张ppt和n个数字，每个数字代表页数，给出每张ppt的位置和页数的位置，每张ppt上都会有一个页数，
问最多能确定多少张ppt和页数一一对应，输出相应的ppt和页数。
分析：
先求出最大匹配 total 和相应的匹配方案。然后依次尝试删除匹配方案中的每条边，再求删除边后的最大匹配res，如果 res<total ，说明这条匹配方案必不可少，否则就是可以去掉的匹配，也就是不能唯一确定的匹配。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
const int MAX_N=30;int n,cases=0,total;
int match[MAX_N],used[MAX_N],edge[MAX_N][MAX_N];
int xmin[MAX_N],xmax[MAX_N],ymin[MAX_N],ymax[MAX_N],x[MAX_N],y[MAX_N];
set<pair<int,int> > s; //s中存储最大匹配ppt编号和相应页数struct Ans{int u,v;bool operator < (const Ans& rhs) const{return u<rhs.u;}
}ans[MAX_N];bool dfs(int v)
{for(int j=0;j<n;j++){ //扫描每个页数if(!used[j]&&edge[v][j]==1){used[j]=1;int u=match[j];if(u==-1||dfs(u)){ //第j页尚未匹配或者已有匹配可以另寻匹配match[j]=v;return true;}}}return false;
}int bipartite()
{int res=0;memset(match,-1,sizeof(match));for(int i=0;i<n;i++){memset(used,0,sizeof(used));if(dfs(i)) {res++;}}return res;
}int main()
{//freopen("Ain.txt","r",stdin);while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++){scanf("%d%d%d%d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);}for(int i=0;i<n;i++){scanf("%d%d",&x[i],&y[i]);}//建图memset(edge,0,sizeof(edge));for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(x[j]>=xmin[i]&&x[j]<=xmax[i]&&y[j]>=ymin[i]&&y[j]<=ymax[i]){edge[i][j]=1;}}}//求最大匹配total=bipartite();s.clear();for(int j=0;j<n;j++){ //将最大匹配方案记录下来if(match[j]!=-1){s.insert(make_pair(match[j],j));}}//printf("total=%d\n",total);//检查匹配int ans_num=0;for(set<pair<int,int> > :: iterator it=s.begin();it!=s.end();it++){pair<int,int> tmp=(*it);int u=tmp.first,v=tmp.second;edge[u][v]=0;//printf("u=%d v=%d check()=%d\n",u,v,bipartite());if(bipartite()!=total){ans[ans_num].u=u;ans[ans_num++].v=v;}edge[u][v]=1;}printf("Heap %d\n",++cases);if(ans_num==0){printf("none");}else {sort(ans,ans+ans_num);for(int i=0;i<ans_num;i++){if(i) printf(" ");printf("(%c,%d)",ans[i].u+'A',ans[i].v+1);}}printf("\n\n");//printf("Time elapse: %.5f\n",1.0*clock()/CLOCKS_PER_SEC);}return 0;
}