POJ1486 Sorting Slides

POJ, 二分匹配

　　题意：给定n个矩形n个点，将矩形和点一一对应，判断是否存在唯一的配对情况。 - 原题链接

　　先找出任意完备匹配，再枚举匹配中的每一条边，若删去该边仍能找到完备匹配，则该该边对应的矩形没有唯一配对方案。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=26+5, maxm=1000+10;
int T, n, ans, from[maxn], rec[maxn];
bool mmp[maxn][maxn], vis[maxn];
struct point
{
	int x, y;
	void sc() {	scanf("%d%d", &x, &y); }
}p[maxn];
struct matrix
{
	int x1, y1, x2, y2;
	void sc() {	scanf("%d%d%d%d", &x1, &x2, &y1, &y2); }
	bool in(point t) {	return x1<=t.x&&t.x<=x2&&y1<=t.y&&t.y<=y2; }
}mat[maxn];
void Read()
{
	for(int i=1; i<=n; i++)	mat[i].sc();
	for(int i=1; i<=n; i++)	p[i].sc();
	return ;
}
bool Dfs(int u)
{
	for(int v=1; v<=n; v++) if(!vis[v] && mmp[u][v])
	{
		vis[v]=true;
		if(!from[v] || Dfs(from[v]))
		{
			from[v]=u;
			return true;
		}
	}
	return false;
}
void debug()
{
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
			cout<<(int)mmp[i][j];
		cout<<endl;
	}
	return ;
}
void Work()
{
	printf("Heap %d\n", ++T);
	memset(mmp, false, sizeof mmp);
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(mat[j].in(p[i]))
				mmp[i][j]=true;
	ans=0;
	memset(from, 0, sizeof from);
	for(int i=1; i<=n; i++)
	{
		memset(vis, false, sizeof vis);
		ans+=Dfs(i);
	}
	if(ans!=n)
	{
		printf("none\n\n");
		return ;
	}
	bool flag=false;
	memcpy(rec, from, sizeof rec);
	for(int i=1; i<=n; i++)
	{
		mmp[rec[i]][i]=false;
		ans=0;
		memset(from, 0, sizeof from);
		for(int j=1; j<=n; j++)
		{
			memset(vis, false, sizeof vis);
			ans+=Dfs(j);
		}
		if(ans!=n)
		{
			if(flag)	printf(" ");
			printf("(%c,%d)", i+'A'-1, rec[i]);
			flag=true;
		}
		mmp[rec[i]][i]=true;
	}
	if(!flag)	printf("none");
	printf("\n\n");
	return ;
}
int main()
{
	while(scanf("%d", &n)!=EOF&&n)	Read(), Work();
	return 0;
}