烦人的幻灯片问题（类拓扑排序）

问题描述

李教授将于今天下午作一次非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n≤26），这n张幻灯片按照演讲要使用的顺序已经用数字1，2，…，n在上面编了号。因为幻灯片是透明的，所以我们用大写字母A，B，C，…再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若是出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们就称对应是无法实现的。

输入文件（slides.in）

文件的第1行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数Xmin，Xmax，Ymin，Ymax（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，…，再接下来的n行依次为n个数字编号的坐标x，y，显然在幻灯片之外是不会有数字的。

输出文件（slides.out）

若是对应可以实现，则输出文件包括n行，每一行一个字母和一个数字，中间一个空格，各行以字母的升序排列；若是对应无法实现，在文件的第一行顶格输出None即可。

样例输入

4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11

样例输出

A 4
B 1
C 2
D 3

#include<iostream>
#include<vector>

using namespace std;

int xmin[100],xmax[100],ymin[100],ymax[100];//记录每个幻灯片的坐标 
int xx[100],yy[100];//记录每个数字的坐标 
int pd[100];//第i个数字被pd[i]个幻灯片指向 
int ans[100];//第i个幻灯片指向第ans[i]个幻灯片 
int n;//n个幻灯片和n个数字 
vector<int> map[100];//向量容器建图 

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) pd[i]=0;//初始化pd数组 
    for(int i=1;i<=n;i++)
      cin>>xmin[i]>>xmax[i]>>ymin[i]>>ymax[i];//输入每个幻灯片的坐标 
    for(int i=1;i<=n;i++)
      cin>>xx[i]>>yy[i];//输入每个数字的坐标 
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(xmin[i]<=xx[j]&&xmax[i]>=xx[j]&&ymin[i]<=yy[j]&&ymax[i]>=yy[j]){ 
          map[i].push_back(j);//如果第j个字母在第i个幻灯片内，则i->j 
          pd[j]++;//记录第i个数字被几个幻灯片指向  
        }  
    bool t=true;//t=true表示有解 
    int tot=0;//表示已有tot个幻灯片被确认对应数字 
    while(t==true||tot<n){
        t=false;//如果无法进一步确认，则t返回到while的值为true 
        for(int i=1;i<=n;i++)
          if(pd[i]==1){//找被唯一幻灯片指向的数字 
            for(int x=1;x<=n;x++)
              for(int y=0;y<map[x].size();y++){
                if(map[x][y]==i){//x为所求的幻灯片的标号 
                    for(int j=0;j<map[x].size();j++)
                      pd[map[x][j]]--;//x指向的所有数字的被指向数-1
                    map[x].clear();//相当于删除x这个点
                    t=true;//当前循环中进一步确认了一个幻灯片的数字 
                    tot++;//又有一个幻灯片被确认 
                    ans[x]=i;//x幻灯片->i数字 
                }
              }
          }
    }
    if(tot!=n) cout<<"None"<<endl;
      else 
        for(int i=1;i<=n;i++){
            char ch;
            ch=i+64;
            cout<<ch<<" "<<ans[i]<<endl;
        }//输出 
    return 0;
}