【题解】CF906C：Party_v c cffxx906-CSDN博客

本文链接：https://blog.csdn.net/ModestCoder_/article/details/108630861

本文介绍了一种使用状态压缩动态规划（状压DP）解决特定社交圈问题的方法。通过对01状态进行压缩，利用位运算高效地表示和更新个体间的社交关系，解决了在给定的人际关系网中寻找最小社交圈覆盖的问题。文章详细阐述了算法思路，并提供了完整的代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

原题传送门
状压
01状态中所有1表示互相认识
$sta_i$ 表示初始 $i$ 的交际圈，如果 $i$ 在状态 $J$ 中，可以直接把 $sta_i$ 的状态直接并入 $J$ ，表示选择 $i$ ，把他认识的人都互相认识一遍

然后记录路径， $id_J$ 表示该状态是通过选择 $id_J$ 这个人来的， $pre_J$ 表示上个状态

Code：

#include <bits/stdc++.h>
#define maxn 5000010
#define maxm 25
using namespace std;
const int inf = 1e9;
int power[maxm], n, m, sta[maxm], dp[maxn], id[maxn], pre[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	n = read(), m = read();
	if (m == n * (n - 1) / 2) return puts("0"), 0;
	power[0] = 1;
	for (int i = 1; i <= n; ++i) power[i] = power[i - 1] << 1;
	for (int i = 1; i <= n; ++i) sta[i] = power[i - 1];
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read();
		sta[x] |= power[y - 1], sta[y] |= power[x - 1];
	}
	for (int i = 1; i <= power[n] - 1; ++i) dp[i] = inf;
	for (int i = 1; i <= n; ++i) dp[sta[i]] = 1, id[sta[i]] = i;
	for (int i = 0; i < power[n]; ++i){
		if (dp[i] == inf) continue;
		for (int j = 1; j <= n; ++j)
			if ((i & power[j - 1]) && (dp[i | sta[j]] > dp[i] + 1)){
				dp[i | sta[j]] = dp[i] + 1,
				id[i | sta[j]] = j,
				pre[i | sta[j]] = i;
			}
	}
	n = power[n] - 1;
	printf("%d\n", dp[n]);
	while (n) printf("%d ", id[n]), n = pre[n];
	return 0;
}