如何做体育彩票网站/企业培训权威机构

[0517]图论算法学习笔记(Ⅲ)
Note by shy.
图论最短路径与最生成树练习题(JSOI P1011,P1014)
A层次第二讲：烦人的幻灯片问题（slides）
背景 Background
A层次第二讲第四题
描述 Description
李教授将于今天下午作一次非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n≤26），这n张幻灯片按照演讲要使用的顺序已经用数字1，2，…，n在上面编了号。因为幻灯片是透明的，所以我们用大写字母A，B，C，…再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若是出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们就称对应是无法实现的。
输入格式 Input Format
文件的第1行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数Xmin，Xmax，Ymin，Ymax（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，…，再接下来的n行依次为n个数字编号的坐标x，y，显然在幻灯片之外是不会有数字的。
输出格式 Output Format
若是对应可以实现，输出文件应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且各行以字母的升序排列，注意输出的字母要大写并且顶格；反之，若是对应无法实现，在文件的第一行顶格输出None即可。行首行末并无多余的空格。
样例输入 Sample Input
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
样例输出 Sample Output
A 4
B 1
C 2
D 3
时间限制 Time Limitation
各个测试点1s
注释 Hint
各个测试点1s
Accepted Code For CPP: 
#include<stdio.h>  
#include<stdlib.h>  
#include <iostream.h>
using namespace std; 
struct ss  
{  
       int x,y;  
} ans[40];  
int a[30][4],b[30][2],tot[30];  
bool v[30][30],v_shu[30],v_square[30];  
int n,x1,x2,y1,y2,remain;  
int cmp(const void*a,const void*b)  
{  
    ss c=*(ss*)a,d=*(ss*)b;  
    if (c.x<d.x) return -1;  
    if (c.x>d.x) return 1;  
    return 0;  
}  
bool inin(int x,int y)  
{  
     if ((b[x][0]>=a[y][0]&&b[x][0]<=a[y][1])&&(b[x][1]>=a[y][2]&&b[x][1]<=a[y][3]))  
        return 1;  
     return 0;  
}  
int main()  
{  
    scanf("%d",&n);  
    for (int i=1;i<=n;++i)  
    {  
        scanf("%d%d%d%d",&x1,&x2,&y1,&y2);  
        a[i][0]=x1; a[i][1]=x2; a[i][2]=y1; a[i][3]=y2;  
    }  
    for (int i=1;i<=n;++i)  
    {  
        scanf("%d%d",&x1,&y1);  
        b[i][0]=x1; b[i][1]=y1;  
    }  
    for (int i=1;i<=n;++i)  
        for (int j=1;j<=n;++j)  
            if (inin(i,j))  
            {  
                          v[i][j]=1;  
                          ++tot[i];  
            }  
    remain=n;  
    while (1)  
    {  
          int k=0;  
          for (int i=1;i<=n;++i)  
              if ((tot[i]==1)&&(!v_shu[i]))  
              {  
                                           k=i;  
                                           break;  
              }  
          if (k==0)   
             if (remain!=0)  
             {  
                          cout<<"None"<<endl;
                           return 0;  
             }  
             else break;  
          v_shu[k]=true;  
          --remain;  
          int die;  
          for (int i=1;i<=n;++i)  
              if (v[k][i])  
              {  
                          die=i;  
                          break;  
              }  
          for (int i=1;i<=n;++i)  
              if (v[i][die])  
              {  
                            v[i][die]=0;  
                            --tot[i];  
              }  
          ans[n-remain].y=k;  
          ans[n-remain].x=die;  
    }  
    qsort(ans,n+1,sizeof(ss),cmp);  
    for (int i=1;i<=n;++i)  
    {
        printf("%c",ans[i].x+'A'-1);  
          cout << " " ;
         cout <<ans[i].y<<endl;         
        }       
    return 0;  
}