Sorting Slides
Description
Professor
Clumsey is going to give an important talk this afternoon.
Unfortunately, he is not a very tidy person and has put all his
transparencies on one big heap. Before giving the talk, he has to sort
the slides. Being a kind of minimalist, he wants to do this with the
minimum amount of work possible.
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
題意：有編號的幻燈片是透明的，疊在一起的時候，除了沒被覆蓋的編號，其他的編號被多張幻燈片覆蓋時就分不清哪個編號是哪張的。
但能通過確定的幻燈片的編號（編號只被一張幻燈片覆蓋，這個編號就是該幻燈片的）來用排除法確定其他幻燈片的編號。
求：是否能確定所有幻燈片的編號。如果可以，對每張幻燈片，判斷這個編號是否是唯一的。對唯一編號幻燈片輸出編號。
分析：這個直接是比較明顯的二分圖最大匹配。首先肯定是選取唯一確定的幻燈片不用，接下來就是交叉路徑求可增光路的事了。整個過程就是匈牙利算法。
求出匹配方案M，對M中每次刪除一個邊，再次通過該邊的一點看看是否有可增光路，有則會再次達到最大匹配，這說明該編號對應的可選矩形不唯一。
#include <iostream>
#define maxn 1000
using namespace std;
struct T
{
int x1, x2, y1, y2;
}reg[maxn];
int mat[maxn][maxn], hash[maxn], pre[maxn], path[maxn];
int n;
int more(int u)
{
int i;
for (i = 0; i < n; i++)
{
if (hash[i] == 0 && mat[u][i])
{
hash[i] = 1;
if (pre[i] == -1 || more(pre[i]))
{
pre[i] = u;
return 1;
}
}
}
return 0;
}
int eft()
{
int i, j, num;
for (i = 0; i < n; i++) pre[i] = -1;
for (i = 0, num = 0; i < n; i++)
{
for (j = 0; j < n; j++) hash[j] = 0;
if (more(i))
{
num++;
}
}
return num;
}
int main()
{
int i, j, x1, x2, y1, y2, x, y, num, sign, ca = 0, m;
while (scanf("%d", &n), n)
{
ca++;
for (i = 0; i < n; i++)
{
scanf("%d%d%d%d", ®[i].x1, ®[i].x2, ®[i].y1, ®[i].y2);
}
for (i = 0; i < n; i++)
{
scanf("%d%d", &x, &y);
for (j = 0; j < n; j++)//編號被幻燈片上覆蓋的，編號跟其連邊，表示該編號可能在該幻燈片上
{
if (x > reg[j].x1 && x < reg[j].x2 && y > reg[j].y1 && y < reg[j].y2)
{
mat[i][j] = 1;
}
else
{
mat[i][j] = 0;
}
}
}
num = eft();
sign = 0;
printf("Heap %d\n", ca);
if (num == n)//能找到一種方案讓每個編號對應一個幻燈片
{
for (i = 0; i < n; i++)
{
path[i] = pre[i];
}
for (i = 0; i < n; i++)
{
mat[path[i]][i] = 0;//刪邊
if (eft() == num)//如果能再次達到最大匹配M，則編號跟幻燈片不是唯一的
{
continue;
}
else
{
if (sign)
{
printf(" ");
}
printf("(%c,%d)", 'A' + i, path[i] + 1);//否則，輸出唯一對應的幻燈片跟編號。
sign = 1;
}
mat[path[i]][i] = 1;
}
}
if (!sign)
{
printf("none");
}
printf("\n\n");
}
return 0;
}