欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

[CF906C]Party

程序员文章站 2022-04-01 11:28:51
1h左右。...

题目

传送门 to luogu

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

数据范围与提示
n22n\le 22 ,无重边、自环。

思路

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

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

画一个图,更好理解。

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

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

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

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

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

代码

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