1624.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1624 on 2005-12-29 at 11:32:00 */ 
#include <cstdio>
#include <cstring>

const int MAX = 32;

class Slide {
private:
	int l, r, d, u;
public:
	void make();
	bool mark(int, int) const;
};
void Slide::make() {
	scanf("%d %d %d %d", &l, &r, &d, &u);
}
bool Slide::mark(int x, int y) const {
	return (x > l && x < r && y > d && y < u);
}

bool suit[MAX][MAX];
bool check[MAX];
int match[MAX], n;

int Hung_Match(int, int);
bool DFS(int);

int main()
{
	Slide silde[MAX];
	int i, j, t;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		memset(suit, false, sizeof(suit));
		for(i = 0; i < n; i++) silde[i].make();
		for(i = 0; i < n; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			for(j = 0; j < n; j++) {
				if(silde[j].mark(x, y)) suit[j][i] = true;
			}
		}
		printf("Heap %d\n", t);
		bool print = false;
		for(i = 0; i < n; i++) {
			int m = -1;
			for(j = 0; j < n; j++) {
				if(suit[i][j] && Hung_Match(i, j) == n-1) {
					if(m == -1) m = j;
					else { m = -1; break; }
				}
			}
			if(m != -1) {
				if(print) putchar(' ');
				print = true;
				printf("(%c,%d)", i+'A', m+1);
			}
		}
		if(!print) printf("none");
		printf("\n\n");
	}
	
	return 0;
}

int Hung_Match(int p, int e)
{
	int i, cer = 0;
	memset(match, -1, sizeof(match));
	for(i = 0; i < n; i++) {
		memset(check, false, sizeof(check));
		check[e] = true;
		if(i != p && DFS(i)) cer++;
	}
	return cer;
}
bool DFS(int p)
{
	int i;
	for(i = 0; i < n; i++) {
		if(!check[i] && suit[p][i]) {
			check[i] = true;
			int t = match[i];
			match[i] = p;
			if(t == -1 || DFS(t)) return true;
			match[i] = t;
		}
	}
	
	return false;
}