題目

傳送門 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$ 相連？任取 $y\in S$ ，$S-\{y\}+\{x\}$ 是「團」，且 $x,y$ 相連。

程式碼

不想寫極大值 $\tt 0x3f$ 。利用每個點最多操作一次的性質，得出答案最大爲 $n$ 。實際上應該是 $n-2$ ，在一條鏈的情況下。然後用 $n$ 當了 $\tt dp$ 初值。

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
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;
}
template < class T >
void getMax(T&a,const T&b){if(a<b)a=b;}
template < class T >
void getMin(T&a,const T&b){if(b<a)a=b;}

const int MaxN = 22;
int dp[1<<MaxN], cnt[1<<MaxN];
int g[1<<MaxN]; // 狀壓後的鄰接矩陣
int lst[1<<MaxN], ans[1<<MaxN]; // 還原方案

void print(int S){
	if(dp[S] == 0) return ;
	print(lst[S]); printf("%d ",ans[S]+1);
}
int main(){
	int n = readint(), m = readint();
	for(int i=0; i<(1<<n); ++i){
		if(i != (i&-i))
			dp[i] = n;
		if(i) cnt[i] = cnt[i-(i&-i)]+1;
	}
	while(m --){
		int a = readint()-1;
		int b = readint()-1;
		g[a] |= 1<<b, g[b] |= 1<<a;
		dp[(1<<a)|(1<<b)] = 0;
	}
	for(int i=3; i<=n; ++i)
	for(int S=1; S<(1<<n); ++S){
		if(cnt[S] <= 2) continue;
		int r = S&-S, S_ = S-r;
		if(!dp[S_] && !dp[r^(S_&-S_)])
		if(!dp[S_-(S_&-S_)+r])
			dp[S] = 0; // 天生「團」
	}
	for(int i=2; i<n; ++i)
	for(int S=1; S<(1<<n); ++S)
	if(cnt[S] == i) // 向前更新
	for(int j=0; j<n; ++j)
	if(S>>j&1){ // 試圖對j進行操作
		int S_ = S|g[j];
		if(dp[S_] >= dp[S]+1){
			dp[S_] = dp[S]+1;
			lst[S_] = S, ans[S_] = j;
		}
	}
	printf("%d\n",dp[(1<<n)-1]);
	print((1<<n)-1);
	return 0;
}