4242160_mle.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 62 行

#include <stdio.h>
#include <algorithm>

using namespace std; 

int f[21][1 << 20]; 
int like[21][21]; 

int num(int v) 
{ 
	int ret = 0; 

	while (v) 
	{ 
		v &= v - 1; 
		ret++; 
	} 
	return ret; 
} 

int main() 
{ 
	int j, n, m; 
	int i, p, t, k; 

	scanf("%d%d", &n, &m); 
	memset(like, 0, sizeof like); 
	for (i = 1; i <= n; i++) 
	{ 
		scanf("%d", &p); 
		while (p--) 
		{ 
			scanf("%d", &t); 
			like[i][t] = 1; 
		} 
	} 
	int mx = 1 << m; 
	fill_n(f[0], mx, 1); 
	for (i = 1; i <= n; i++) 
	{ 
		for (j = 0; j < mx; j++) 
		{ 
			f[i][j] = 0; 
			if (num(j) != i) 
				continue; 
			for (k = 0; k < m; k++) 
			{ 
				if ((j & (1 << k)) && like[i][k + 1]) 
				{ 
					f[i][j] += f[i - 1][j ^ (1 << k)]; 
				} 
			} 
		}  
	} 
	int ans = 0; 
	for (i = 0; i < mx; i++) 
	{ 
		ans += f[n][i]; 
	} 
	printf("%d\n", ans); 
	return 0; 
}