1335.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1335 on 2005-12-28 at 16:40:16 */ 
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

const int MAX = 32;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

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

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

int main()
{
	map<const char*, int, cmp> id, man;
	char ids[MAX][MAX], mans[MAX][MAX], ch;
	int t, T, i, j;
	bool hide[MAX], print[MAX];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		if(t != 0) putchar('\n');
		id.clear(); man.clear();
		scanf("%d", &n);
		for(i = 0; i < n; i++) {
			scanf("%s\n", ids[i]);
			id[ids[i]] = i;
		}
		int mn = 0, o;
		memset(suit, true, sizeof(suit));
		memset(hide, false, sizeof(hide));
		while((ch = getchar()) != 'Q') {
			scanf("%s\n", mans[mn]);
			switch(ch) {
			case 'E':
				if(man.count(mans[mn]) == 0) o = man[mans[mn]] = mn, mn++;
				else o = man.find(mans[mn])->second;
				hide[o] = true;
			break;
			case 'M':
				o = id.find(mans[mn])->second;
				for(i = 0; i < n; i++) {
					if(!hide[i]) suit[i][o] = false;
				}
			break;
			case 'L':
				o = man.find(mans[mn])->second;
				hide[o] = false;
			break;
			}
		}
		memset(print, false, sizeof(print));
		for(i = 0; i < n; i++) {
			int f = -1;
			for(j = 0; j < n; j++) {
				if(!print[j] && (f == -1 || strcmp(mans[j], mans[f]) < 0)) f = j;
			}
			print[f] = true;
			printf("%s:", mans[f]);
			int m = -1;
			for(j = 0; j < n; j++) {
				if(suit[f][j] && Hung_Match(f, j) == n-1) {
					if(m == -1) m = j;
					else { m = -1; break; }
				}
			}
			if(m == -1) printf("???\n");
			else printf("%s\n", ids[m]);
		}
	}
	
	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;
}