狗狗40题搞完纪念 » 1018

1018
1018.cpp


#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 32;

struct Hungray {
	int nx, ny, mx[MAXN], my[MAXN];
	bool e[MAXN][MAXN];

	bool mark[MAXN];

	bool augment(int i) {
		if (!mark[i]) {
			mark[i] = true;
			for (int j = 0; j < ny; ++j) {
				if (e[i][j]) {
					if (my[j] == -1 || augment(my[j])) {
						mx[i] = j;
						my[j] = i;
						return true;
					}
				}
			}
		}
		return false;
	}

	int gao() {
		int ret = 0;
		fill(mx, mx + nx, -1);
		fill(my, my + ny, -1);
		for (int i = 0; i < nx; ++i) {
			fill(mark, mark + nx, false);
			if (augment(i)) {
				++ret;
			}
		}
		return ret;
	}
};

int main() {
	Hungray bg;
	int ans[MAXN], x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN], x, y, ri = 0;

	while (scanf("%d", &bg.nx) != EOF && bg.nx > 0) {
		bg.ny = bg.nx;
		for (int i = 0; i < bg.nx; ++i) {
			scanf("%d%d%d%d", &x1[i], &x2[i], &y1[i], &y2[i]);
		}
		for (int j = 0; j < bg.ny; ++j) {
			scanf("%d%d", &x, &y);
			for (int i = 0; i < bg.nx; ++i) {
				bg.e[i][j] = x1[i] < x && x < x2[i] && y1[i] < y && y < y2[i];
			}
		}

		x = bg.gao();
		y = 0;
		copy(bg.mx, bg.mx + bg.nx, ans);

		printf("Heap %d\n", ++ri);
		for (int i = 0; i < bg.nx; ++i) {
			if (ans[i] != -1) {
				bg.e[i][ans[i]] = false;
				if (bg.gao() < x) {
					if (y > 0) {
						putchar(' ');
					}
					printf("(%c,%d)", 'A' + i, 1 + ans[i]);
					++y;
				}
				bg.e[i][ans[i]] = true;
			}
		}
		puts(y == 0 ? "none\n" : "\n");
	}
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//293 	2010-06-27 06:49:49 	Accepted 	1018 	C++ 	0 	180 	anotherpeg 	Source
Leave a Reply