2243.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2243 on 2006-05-22 at 20:19:40 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int BN = 10;
const int MN = 256;

class Material {
public:
	int dis[BN], k;
	Material() { memset(dis, 0, sizeof(dis)); }
	void make();
	bool contain(const Material&) const;
	void mix(const Material&);
	bool operator <(const Material& m) const { return k < m.k; }
	bool operator ==(const Material&) const;
};
void Material::make() {
	int i; scanf("%d", &k);
	memset(dis, 0, sizeof(dis));
	for(i = 0; i < k; i++) {
		int o; scanf("%d", &o); o--;
		dis[o>>5] |= 1 << (o&31);
	}
}
bool Material::contain(const Material& m) const {
	int i;
	for(i = 0; i < BN; i++)
		if((dis[i] | m.dis[i]) != dis[i]) return false;
	return true;
}
void Material::mix(const Material& m) {
	int i;
	for(i = 0; i < BN; i++) dis[i] |= m.dis[i];
}
bool Material::operator ==(const Material& m) const {
	int i;
	for(i = 0; i < BN; i++)
		if(dis[i] != m.dis[i]) return false;
	return true;
}

int main()
{
	Material mat[MN];
	int i, j, n, m;
	
	while(scanf("%d %d", &n, &m) != EOF) {
		for(i = 0; i < m; i++) mat[i].make();
		sort(mat, mat+m);
		int rn = 0;
		for(i = 0; i < m; i++) {
			Material mr;
			for(j = 0; j < i; j++)
				if(mat[i].contain(mat[j])) mr.mix(mat[j]);
			if(mat[i] == mr) rn++;
		}
		printf("At most %d test material(s) can be removed.\n", rn);
	}
	
	return 0;
}