[CF906C]Party

题目

传送门 to luogu

题意概要
“团”的定义是，该子图为完全图。现有 $n$ 点 $m$ 边无向图，每次选择一个点，使得其周围的点形成一个“团”。即，任意两个与该点相邻的点，连上一条边。问最少操作多少次，使得整张图为完全图。

数据范围与提示
$n\le 22$ ，无重边、自环。

思路

不难发现过程大概是这样的：选择一个点以后，对于一个包含该点的“团”，加入与该点相邻的点。一开始有很多个“团”，然后在不断的操作中变大（或者多个团合成了一个团），最终包含整张图。

我们是否可以只追踪这一个“团”的变化呢？是可以的。这里给出一种证明方式。我们本来要操作“团”中的一个点，以此加入与其相邻的点。如若它相邻的点变多了，那一定是一个与其相邻的点先被操作。

画一个图，更好理解。

x-----y
 \   /
  \ /
   z

我们原先要操作 $x$ ，其时 $x,z$ 不相连，但是操作 $y$ 使得 $x,z$ 相连。这样做是否有合理之处？

完全可以更改为先操作 $x$ 再操作 $y$ 。先操作 $x$ 时，$y$ 加入了“团”，然后操作 $y$ 就使 $z$ 加入了“团”。跟先操作 $y$ 的效果是一样的。所以，我们先操作 $x$ ，也存在一种方式得到最优解。

$\tt dp$ 思路已经出现。用 $f(S)$ 表示，$S$ 集合中的点形成“团”所需最小操作次数。建议刷表法，枚举进行一次何种操作。输出方案存前驱即可。复杂度 $\mathcal O(n2^n)$ 。

求“团”怎么求？若 $x\in S$ ，则 $S$ 是“团”的充要条件是，$S-\{x\}$ 是“团”，$S-\{x\}$ 中任意一个点都与 $x$ 相连。怎么判断是否 $S$ 中每个点都与 $x$ 相连？咱不是用状压的邻接矩阵吗，难道这都做不到？

代码

不想写极大值 $\tt 0x3f$ 。利用每个点最多操作一次的性质，得出答案最大为 $n$ 。实际上应该是 $n-2$ ，在一条链的情况下。然后用 $n+1$ 当了 $\tt dp$ 初值。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 22;
int dp[1<<MaxN], g[1<<MaxN];
int pre[1<<MaxN], ans[1<<MaxN]; // 还原方案

void paint(int S){
	if(dp[S] == 0) return ; // 生而为人 我很抱歉
	paint(pre[S]), printf("%d ",ans[S]+1);
}

int main(){
	int n = readint(), m = readint();
	for(int i=1,a,b; i<=m; ++i){
		a = readint()-1, b = readint()-1;
		g[a] ^= 1<<b, g[b] ^= 1<<a;
	}
	for(int S=1; S<(1<<n); ++S){
		dp[S] = n+1; // 极大值
		for(int i=0; i<n; ++i)
			if(S>>i&1){
				int S_ = S^(1<<i);
				if((S_&g[i]) == S_)
					dp[S] = dp[S_];
				break; // 小剪枝
			}
	}
	for(int S=1; S<(1<<n); ++S)
	for(int i=0; i<n; ++i) if(S>>i&1)
		if(dp[S|g[i]] > dp[S]+1){
			dp[S|g[i]] = dp[S]+1;
			pre[S|g[i]] = S, ans[S|g[i]] = i;
		}
	printf("%d\n",dp[(1<<n)-1]);
	paint((1<<n)-1);
	return 0;
}

本文地址：https://blog.csdn.net/qq_42101694/article/details/107892185