上午
讲了搜索,最短路,最小生成树
关于搜索
首先是bfs一些走迷宫问题
基本框架如下:
1.入队,打上标记
2.队列不空{
取出当前队首节点,接近着pop
一般都是对队首枚举四个方向{
对于每个方向拓展出来的点
进行一大堆特判
留下经过挑选的数 {
入队
打上标记
}
}
}
3.善后
一般而言 bfs比较好理解也好实现
对于dfs,dfs就比较操蛋一些,因为掺杂了递归
我依稀记得一个名人沃乱硕得曾经说过:对于任何一个算法,掺杂了递归,就不是一个好算法
dfs基本框架如下:
到达了边界 返回
一些操蛋剪枝优化包括什么A*IDA*
一般到了这里都会有一些条件,比如在一个for里去搜索,或者在if里去搜索
直接来裸搜索的不太多
搜索有好多可做题呢,矩形覆盖 数独
还没接到例题,等收到了再补上吧
最短路
首先是弗洛伊德 三个for
就很nb....
其中k必须在外边,因为我们必须要用已经更新过的点去更新别的,我们不可能用一个未更新的点去更新别人
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)与有向图
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)的题
只敲了个别几个,好几个没敲
然后就是改题了......