poj 1486 Sorting Slides(二分匹配) - c++编程基础

题意：有n个大小不等透明的幻灯片（只有轮廓和上面的数字可见）A、B、C、D、E…按顺序叠放在一起，现在知道每个幻灯片大小，由于幻灯片是透明的，所以能看到幻灯片上的数字（给出了每个数字的坐标，但不知道这些数字分别属于哪个幻灯片），现在要你根据当前的已知信息，输出能够确定的幻灯片编号和数字的匹配。

思路：很明显的二分匹配问题，但求的是确定匹配，先求出最大的匹配。然后依次删除每一条边，再求其最大匹配，如果最大匹配减小，说明这匹配是确定的。

 
//168K  0MS  
#include   
#include   
const int M = 30;  
  
struct Slide  
{  
    int x1,x2,y1,y2;  
} slide[M];  
int mat[M][M],link[M],cur[M],vis[M],n;  
  
int DFS(int u)  
{  
    for (int v = 1; v<=n; v ++)  
    {  
        if (!vis[v]&&mat[u][v])  
        {  
            vis[v] = 1;  
            if(link[v] == -1||DFS(link[v]))  
            {  
                link[v] = u;  
                return 1;  
            }  
        }  
    }  
    return 0;  
}  
int MaxMatch()  
{  
    int u,res = 0;  
    memset(link,-1,sizeof(link));  
    for (u = 1; u <= n; u ++)  
    {  
        memset (vis,0,sizeof(vis));  
        if (DFS(u)) res ++;  
    }  
    return res;  
}  
int main ()  
{  
#ifdef LOCAL  
    freopen("in.txt","r",stdin);  
#endif  
    int i,j,x,y;  
    int cnt = 0;  
    while (scanf ("%d",&n)&&n)  
    {  
        memset (mat,0,sizeof(mat));  
        for (i = 1; i <= n; i ++)  
            scanf ("%d%d%d%d",&slide[i].x1,&slide[i].x2,&slide[i].y1,&slide[i].y2);  
        for (i = 1; i <= n; i ++)  
        {  
            scanf ("%d%d",&x,&y);  
            for (j = 1; j <= n; j ++)  
                if (x>slide[j].x1&&xslide[j].y1&&y