Description
The situation is like this. The slides all have numbers written on them according to their order in the talk. Since the slides lie on each other and are transparent, one cannot see on which slide each number is written.
Well, one cannot see on which slide a number is written, but one may deduce which numbers are written on which slides. If we label the slides which characters A, B, C, ... as in the figure above, it is obvious that D has number 3, B has number 1, C number 2 and A number 4.
Your task, should you choose to accept it, is to write a program that automates this process.
Input
The input consists of several heap
descriptions. Each heap descriptions starts with a line containing a single
integer n, the number of slides in the heap. The following n lines contain four
integers xmin, xmax, ymin and ymax, each, the bounding coordinates of the
slides. The slides will be labeled as A, B, C, ... in the order of the
input.
This is followed by n lines containing two integers each, the x-
and y-coordinates of the n numbers printed on the slides. The first coordinate
pair will be for number 1, the next pair for 2, etc. No number will lie on a
slide boundary.
The input is terminated by a heap description starting with n = 0, which should not be processed.
Output
For each heap description in the input
first output its number. Then print a series of all the slides whose numbers can
be uniquely determined from the input. Order the pairs by their letter
identifier.
If no matchings can be determined from the input, just print
the word none on a line by itself.
Output a blank line after each test case.
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
2
0 2 0 2
0 2 0 2
1 1
1 1
0
Sample Output
Heap 1
(A,4) (B,1) (C,2)
(D,3)
Heap 2
none
1 #include <iostream> 2 #include <stdlib.h> 3 #include <stdio.h> 4 #include <memory.h> 5 using namespace std; 6 int n; 7 //------------------------------------------------------------------------ 8 int tab[201][201];//邻接矩阵,第一维对标号,第二维对应幻灯片 9 int state[201],result[201];//stata:是否被搜索过;result:某幻灯片对应的标号 10 int ans;//找到多少匹配 11 //------------------------------------------------------------------------ 12 int find(int x){// 匈牙利算法---增广路部分(给x找匹配，找到就返回1，否则返回0) 13 for(int i=1;i<=n;i++){ 14 if(tab[x][i]==1 && !state[i]){ 15 state[i]=1;//标记为搜索过 16 if(result[i]==0 || find(result[i])){//未被匹配过&&能找到一条增广路 17 result[i]=x;//匹配i,x 18 return 1;//能找到新的匹配 19 } 20 } 21 } 22 return 0; 23 } 24 int XYL(){//匈牙利算法----主程部分(返回最大匹配) 25 ans=0; 26 memset(result,0,sizeof(result)); 27 for(int i=1;i<=n;i++){//从小到大匹配X,如果匹配成功就ans++ 28 memset(state,0,sizeof(state));//清空是否搜索过数组 29 if(find(i)) ans++;//找到新的匹配 30 }//完成后result[i]保存着第i个幻灯片对应的标号 31 return ans; 32 } 33 //------------------------------------------------------------------------ 34 int main(){ 35 int casee=1; 36 while(cin>>n){ 37 memset(tab,0,sizeof(tab)); 38 //输入及预处理(输入数据维护0-1矩阵tab[标号][幻灯片]::从1开始::) 39 int rect[27][4];//n个矩形 40 if(n==0)break; 41 for(int i=1;i<=n;i++)//输入n个矩形 42 for(int j=0;j<4;j++) 43 cin>>rect[i][j]; 44 for(int i=1;i<=n;i++){//输入n个点并填充tab[][]邻接数组 45 int x,y; 46 cin>>x>>y; 47 for(int j=1;j<=n;j++) 48 if(rect[j][0]<x && rect[j][1]>x && rect[j][2]<y && rect[j][3]>y) 49 tab[i][j]=1; 50 } 51 //输出(核心部分) 52 printf("Heap %d\n",casee++); 53 bool ok=0;//标记是否有可以确定的关系，如果没有输出none 54 for(int j=1;j<=n;j++){//枚举所有关系 55 for(int i=1;i<=n;i++){ 56 if(!tab[i][j])continue;//没有关系直接跳过 57 tab[i][j]=0;//将该关系断开求匹配数(如果不是完美匹配，说明该关系唯一!!!)输出 58 if(XYL()<n){ 59 if(ok)printf(" ");//这是输出格式，要注意空格!!! 60 ok=1; 61 char s=j+‘A‘-1; 62 printf("(%c,%d)",s,i); 63 } 64 tab[i][j]=1;//最后再把该关系恢复，看其它关系 65 } 66 } 67 if(!ok) printf("none\n\n"); 68 else printf("\n\n"); 69 }return 0; 70 } 71 //ps:如果想看二分匹配或者搞匈牙利算法模板的话可以参阅我的另一篇博文 72 //----->_<----The Perfect Stall 完美的牛栏(匈牙利算法、最大二分匹配)