图论小结（三）-剪

BFS 优化：

双向BFS注意点：

1. 每轮遍历整层；
2. 每轮选取已搜索点数少的一边搜一层；

DFS 优化：

剪枝
这里以洛谷的p1731生日蛋糕为例
题目背景
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时，要求R_i>R_i+1, R _i>R_i+1; H_i>H_i+1,
_i>H_i+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q= Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）
数据
N（N<=20000），表示待制作的蛋糕的体积为Nπ；M(M<=15)，表示蛋糕的层数为M。
时空限制：1000ms / 128MB
DFS方式
l：当前层数
r：当前半径(最大等于体积的平方根)
h：当前高度(最大等于体积)
rv：当前剩余体积
ts：当前总侧面积
初始：dfs(0, n^0.5, n, n, 0);

void dfs(int l, int r, int h, int rv, int ts)
{
  loop()
  {
    // 剪枝
    dfs(l+1, r-1, h-1, rv-nowV, ts+nowV);
  }
}

剪枝策略

1. 当前面积+剩余层数最小面积 > 最优解，剪
2. 当前体积 < 剩余层数最小体积，剪
3. 当前体积 > 剩余层数最大体积，剪

剩余层数最小面积与剩余的层数有关，而同一层数会重复使用，所以可以考虑开个数组，预处理一下。而层数最多只有15层，15个状态，果断预处理；
剩余层数最小面积也只与剩余层数有关，同理也会重复使用，预处理；
剩余层数最大体积与剩余层数、当前半径、高度都有关，状态数量最多有15x141x20‘000，如果开个int数组需要超过160Mb空间，暴空间了。这里有个问题，就是经过前两种剪枝后，加上条件限制，我们对这个数组的使用是很稀疏的，所以完全没有必要预处理，只需要在dfs中计算就好。