UVA-11825(状压dp)

//选择点集 每个点集都不相交 并且每个点集与它们相连的点能够覆盖原图
//问最多可一次选择多少点集
int	n, m, k, cas;
int a[17];
int f[1 << 17];//该状态下最多可选几个点集
int arr[1 << 17];//该状态的延申状态，是否可以覆盖原图

inline int dfs(int x) {
	if (f[x] != -1)	return f[x];//记忆化

	int ans = 0;
	//i必须是x的子集
	for (int i = x; i; i = ((i - 1) & x))	if (arr[i] == ((1 << n) - 1))	ans = max(ans, dfs(i ^ x) + 1);
	return f[x] = ans;
}

int	main() {

	while (~scanf("%d", &n), n) {
		memset(f, -1, sizeof f);
		memset(a, 0, sizeof a);
		memset(arr, 0, sizeof arr);

		for (int i = 0; i < n; ++i) {
			a[i] |= (1 << i);
			scanf("%d", &m);

			for (int j = 0; j < m; ++j) {
				scanf("%d", &k);
				a[i] |= (1 << k);
			}
		}

		for (int i = 0; i < (1 << n); ++i) {
			for (int j = 0; j < n; ++j) {
				if ((i & (1 << j)))	arr[i] |= a[j];
			}
		}

		dfs((1 << n) - 1);
		printf("Case %d: %d\n", ++cas, f[(1 << n) - 1]);
	}

	return 0;
}

UVA-11825(状压dp)

原文：https://www.cnblogs.com/wanshe-li/p/13757285.html