7.27集训

Posted on Edited on In

#上午

讲了搜索，最短路，最小生成树 ### 关于搜索

首先是bfs一些走迷宫问题

基本框架如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
1.入队，打上标记
2.队列不空{
  取出当前队首节点，接近着pop
  一般都是对队首枚举四个方向{
     对于每个方向拓展出来的点
     进行一大堆特判
     留下经过挑选的数 {
         入队
         打上标记
     }
  }
}
3.善后
一般而言 bfs比较好理解也好实现

对于dfs，dfs就比较操蛋一些，因为掺杂了递归

我依稀记得一个名人沃乱硕得曾经说过：对于任何一个算法，掺杂了递归，就不是一个好算法

dfs基本框架如下:

1
2
3
4
到达了边界 返回
一些操蛋剪枝优化包括什么A*IDA*
一般到了这里都会有一些条件，比如在一个for里去搜索，或者在if里去搜索
直接来裸搜索的不太多

搜索有好多可做题呢，矩形覆盖 数独 还没接到例题，等收到了再补上吧

最短路

首先是弗洛伊德 三个for

就很nb....

其中k必须在外边，因为我们必须要用已经更新过的点去更新别的，我们不可能用一个未更新的点去更新别人

1
2
3
4
for (int k = 1; k <= n; ++ k)
   for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= n; ++ j)
	 f[i][j] = min(f[i][j], f[i][k]+f[k][j]);

dij与SPFA 回头补上

以后尽量用堆优化的dij因为spfa已经死了

下午

讲了讲图论，主要是关于\(Tarjan\)的相关知识

\(Tarjan\)与有向图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dfn[x] = low[x] = ++ tot;
sta[++tp] = x, in[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
   int y = e[i].to;
   if (!dfn[y]) tarian (y), low[x] = min (low[x], low[y]);
   else if (in[y]) low[x] = min (low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
   int y; ++ res;
   do {
      y = sta[tp--], in[y] = 0;
      tar[y] = cnt, scc[cnt].push_back(y);
   }while (x != y);
}

其中的\(else\)里面的\(low[x] = min (low[x], dfn[y])\)引起了争议，因为我交了好几道题，把里面的\(dfs\)改成\(low\)，是没有问题的，但是定义上应该是不相符的

但是学长依然建议我们写\(dfn\)不写\(low\)

\(Tarjan\)与无向图

割点割桥

求割点与割桥的方法

其中割边判定法则为：无向边\((x,y)\)是桥，当且仅当搜索树上存在\(x\)的一个子节点y满足：\(dfn[x] < low[y]\)

其中割点判定法则为：若\(x\)不是搜索树的根节点（深度优先遍历的起点），则\(x\)是割点当且仅当搜索树上存在\(x\)的一个子节点\(y\)，满足\(dfn[x] \leq low[y]\)

以及边双联通分量 与点双

lyd算法竞赛进阶指南P404有，读者亦可自证

晚上

LCA与倍增

lca可以用倍增来求，也可以用树剖来求，但是树剖常数更小

甩两道比较好的LCA例题

大货车

小仓鼠

好像还做了一些\(Tarjan\)的题

生成树

化学考试之神

只敲了个别几个，好几个没敲

然后就是改题了......