UVA663 Sorting Slides（烦人的幻灯片）

李教授将于今天下午做一次非常重要的演讲。不幸的是，他是一个非常不爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。

题目描述：
教授这次演讲一共要用 n 张幻灯片，这 n 张幻灯片按照演讲要使用的顺序已经用数字 1~n 编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母 A,B,C … 再次将幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字和字母编号对应起来，显然这种对应是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称这种对应是无法实现的。

输入格式：
有多组测试数据。每组测试数据，第一行输入一个整数 n，表示有 n 张幻灯片，接下来 n 行，每行包括 4 个整数: x_min,x_max,y_min,y_max ，为幻灯片的坐标（幻灯片默认为矩形）。这 n 张幻灯片按其在输入文件中出现的顺序从前到后依次编号为 A,B,C …，再接下来的 n 行依次为 n 个数字编号的坐标 x,y （保证数字坐标不超出幻灯片的范围）。当 n 等于 0 时，输入结束。

输出格式：
对于每组测试数据，先输出测试数据的序号，若数据有解，按照字母顺序，依次输出每个字母所对应的数字编号，形如：（A,1) 。若无解，输出 none 。
注意：除最后一组数据外，每组数据在答案输出结束后要多输出一个空行

解析

第一次做到这么玄学的题，在《信息学奥赛一本通》拓扑排序一章找到这个习题（却发现标程都是错的），结果用二分图匹配做了出来

蒟蒻感觉思路不太好想，难度大概在蓝题~紫题。。

那是因为UVa输出换行空格万年老坑

#include<cstdio>
#include<cstring>
using namespace std;
#define N 27
int vis[N],match[N],ans[N],x1[N],x2[N],y1[N],y2[N],n,T;
bool g[N][N],flag;

inline bool dfs(int x) {
    for (register int i=1; i<=n; i++)
        if (!vis[i] && g[x][i]) {
            vis[i]=1;
            if (!ans[i] || dfs(ans[i])) {
                ans[i]=x;//第 i 个幻灯片对应数字为 x
                return true;
            }
        }
    return false;
}

inline int find() {//求二分图最大匹配
    int sum=0;
    memset(ans,0,sizeof ans);
    for (register int x=1; x<=n; x++){
            memset(vis,0,sizeof vis);
            if (dfs(x)) sum++;// 总匹配数
    }
    return sum;
}

int main() {
    while(~scanf("%d",&n) && n) {
        if (T) puts("");
        printf("Heap %d\n",++T);
        memset(g,0,sizeof g);

        for (int i=1; i<=n; i++)
            scanf("%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i]);

        for (int i=1,x,y; i<=n; i++) {
            scanf("%d%d",&x,&y);
            for (int j=1; j<=n; j++)
                if (x>=x1[j] && x<=x2[j] && y>=y1[j] && y<=y2[j])
                    g[i][j]=1;//如果数字在幻灯片范围之内的话则连边，有机会匹配
        }

        int tot=find(),flag=0;

自此已求出当前的匹配，但程序还未结束,如果在此输出答案：

    for (int i=1;i<=n;i++) printf("(%c,%d)",i-1+'A',ans[i]);

按照样例数据，你会发现第一组数据已有正确答案，而第二组数据不是none，而输出了匹配情况

这是因为题目还有一个要求：
若出现多种对应的情况，我们称这种对应是无法实现的。

第二组数据中A和B都可以匹配1和2中任意一个，所以对应不唯一

        //接下来我们要去除这种情况

        for (int j=1; j<=n; j++)
            for (int i=1;i<=n; i++)
                if (g[i][j]) {
                    g[i][j]=0;//考虑依次删去每条边，如果有唯一对应，那么至少有一边删去后使匹配数减少
                    if (find()!=tot) {
                        if (flag) printf(" ");
                        else flag=1;
                        printf("(%c,%d)",j-1+'A',i);//如果幻灯片 j 与 数字 i 是唯一搭配，直接输出
                    }
                    g[i][j]=1;
                }
        if (!flag) printf("none");//如果删去任意一边匹配数都不变，则对应不唯一
        puts("");//相当于printf("\n");
    }
    return 0;
}