Codeforces Round #454 (Div. 2, based on Technocup 2018 Elimination Round 4)
E. Party
题意： n 个点，m 条边，操作：选择一个点，把它直接相邻的点相互连通。问最少要多少次操作可把这个图变成完全图。
tags： n 很小， 状压dp
dp[i] 表示要到达状态 i 的最少操作次数。
0 -> (1<<n)-1 个状态，每次用每个点去更新，如果状态 i 通过第 u 个点操作后到达了状态 j， 则 dp[j] = min(dp[j], dp[i]+1) 。
具体的操作就是状压，第 u 个点的操作也是先把它直接相邻的点用一个数存起来。
初始化：要把原本能够到达的状态初始化为 0。
复杂度O(n^2)
// 454E #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 5000005; int n, m, dp[N], f[25], pre[N], prei[N]; int main() { scanf("%d%d", &n, &m); rep(i,1,n) f[i] = 1<<(i-1); int u, v; rep(i,1,m) { scanf("%d%d", &u, &v); f[u] |= (1<<(v-1)); f[v] |= (1<<(u-1)); } mes(dp, INF); int tmp; rep(ca, 1, (1<<n)-1) // 初始化 { tmp = ca; rep(i,1,n) if( ca>>(i-1)&1 ) tmp &= f[i]; if(tmp == ca) // 如果用所有点与操作后状态不变，那就说明原本就可到达 dp[ca]=0, pre[ca]=-1; } rep(ca, 1, (1<<n)-1) // 状态转移 { rep(i,1,n) if( (ca>>(i-1))&1 && dp[ca]+1<dp[ca|f[i]]) { dp[ca|f[i]] = dp[ca]+1; pre[ca|f[i]] = ca; prei[ca|f[i]] = i; } } printf("%d ", dp[(1<<n)-1]); for(int t=(1<<n)-1; pre[t]!=-1; t=pre[t]) printf("%d ", prei[t]); return 0; }