题目

传送门 to luogu

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

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

思路

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

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

画一个图，更好理解。

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

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

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

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

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

代码

不想写极大值 0 x 3 f \tt 0x3f 0x3f 。利用每个点最多操作一次的性质，得出答案最大为 n n n 。实际上应该是 n − 2 n-2 n−2 ，在一条链的情况下。然后用 n + 1 n+1 n+1 当了 d p \tt dp 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