2295.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2295 on 2006-07-25 at 19:16:44 */ 
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N = 512;
const int L = 128;
 
struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};
 
map<char*, int, cmp> music, fav;
char favr[N][L], sty[N][L];
int mn, fn;
 
int order(map<char*, int, cmp>&, char*, int&);
 
class Person {
public:
	int h, s, m, f;
	bool make(int);
	bool couple(const Person&) const;
};
bool Person::make(int o) {
	char sex;
	scanf("%d\n%c %s %s", &h, &sex, sty[o], favr[o]);
	s = (sex == 'M' ? 0 : 1);
	m = order(music, sty[o], mn);
	f = order(fav, favr[o], fn);
	return sex == 'M';
}
bool Person::couple(const Person& p) const {
	if(abs(h-p.h) > 40)  return false;
	else if(m != p.m) return false;
	else if(f == p.f) return false;
	return true;
}
 
int pn, match[N];
bool cop[N][N], check[N];
 
bool dfs(int);
 
int main()
{
	Person p[N];
	int t, T, i, j;
	int n, fo[N], fon, mo[N], mon;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		fn = mn = fon = mon = 0;
		music.clear(); fav.clear();
		for(i= 0; i < n; i++)
			if(p[i].make(i)) fo[fon++] = i;
			else mo[mon++] = i;
		memset(cop, false, sizeof(cop));
		for(i = 0; i < fon; i++)
			for(j = 0; j < mon; j++)
				if(p[fo[i]].couple(p[mo[j]])) cop[i][j] = true;
		pn = max(fon, mon);
		int mch = 0;
		memset(match, -1, sizeof(match));
		for(i = 0; i < pn; i++) {
			memset(check, false, sizeof(check));
			if(dfs(i)) mch++;
		}
		printf("%d\n", n-mch);
	}
	
	return 0;
}
 
int order(map<char*, int, cmp>& m, char* s, int& o)
{
	if(m.count(s) == 0) m[s] = o++;
	return m.find(s)->second;
}
bool dfs(int o)
{
	int i;
	for(i = 0; i < pn; i++) {
		if(cop[o][i] && !check[i]) {
			check[i] = true;
			int t = match[i];
			match[i] = o;
			if(t == -1 || dfs(t)) return true;
			match[i] = t;
		}
	}
	return false;
}