HDU 5952 Counting Cliques

ACM/ICPC 2016 沈阳站 Counting Cliques
这道题蛮可惜的,其实就是暴力,不过在现场zyyyyy使用了set实现,实际上用vector就过了。

题意

求一个N(N ≤ 100)点M(N ≤ 1000)边的无向图容量为S的团的个数。已知每个点的度不大于20。

思路

代码所示,进行dfs,dfs维护一个conn数组用来表示一个大小为sz的完全图的所有点。在每层的dfs中每次寻找并添加一个可能的点,这个点必须要满足和已有的完全图能够成一个新的大小为sz+1的完全图(也就是和完全图中的所有其他点的都要有边)。
在实现过程中有以下优化:

  • 为了避免重复,只从边号小到边号大建边
  • 为了节约时间,筛掉度小于S-1的边
  • 为了节约时间,第一层dfs完毕后将该点的从图中去掉。
  • 去掉以上两个优化在hdu上还是能过。