Moench 的算法宝库

Floyd思想和倍增思想例题：345.牛站 时间复杂度： O(n^3*logm) 算法思路： Floyd思想： 状态表示：d[K][i][j]为从i到j的经过前K条边的路径的最小值(与Floyd的d[n][i][j]经过前n个点的表示方法略有不同) 状态计算：d[K][i][j] = d[a][i][k] + d[b][k][j]，其中k为经过前a条边后的点， 更新一次可以增加两条边，更新两次增加三条边，如此我们仅需更新m-1次即可得到d[m][S][E]，时间复杂度为：O(n^3*m) n为200，m为1e6必定TLE 可以用倍增思想来将时间复杂度化为logm 倍增思想(快速幂思想) 最终路径类似于：S->x1->x2->x3->……->……->xm-1->E, 中间经过了m-1个点，m条边 我们可发现上述的路径先计算与后计算不会相互影响，即可以先计算中间的或先计算后面的，具有结合律，如此可借助倍增思想，仅需logm次即可找到合法路径 时间复杂度：O(n^3*logm) 具体实现： 哈希所有用过的点，包括起点和终点 倍增算法 代 ...

Floyd 算法求最小环算法思路 DP思路 状态表示：化整为零：按照环上的最大点的编号来分类，可保证不重不漏 状态计算：枚举和最大点相邻的两点i,j同时使得dist[i][j]距离最小，即可保证最小环i->k->j->i的权值最小 证明算法步骤2的正确性： 若枚举到最大点k时，按照如上所述的方法找到最小环上的一个点大于k看，假设为k+2，则我们在该点k处用所有小于k的点i,j找到的最小环，一定不是全局的最优解，当我们枚举到 k+2 时，方可枚举到全局最小换，反证成立，则算法成立 具体实现 每次floyd更新最外层的k时，已知的路径中，只含0~k-1这些点更新的路径，如此可求得环上的最大值为k时的最小环。 求最小环权值：枚举与k相邻的i,j(小于k)，使dist[i][j]最小，即为环上最大点为k的最小环的权值，依次更新k直到k等于n，算法结束 求最小环路径：记录pos[i][j]为 [i, j] 区间，是由pos[i][j]更新而来，每次更新答案，递归求解路径 代码如下：1234567891011121314151617181920212223242526 ...

传递闭包时间复杂度： O(n^3) 算法解释：若 a->b, b->c 则 a->c，将所有的间接到的点化为直接到，如此称为传递闭包算法思路 直接Floyd算法 更新距离的函数变一下即可 代码如下：1234567891011121314151617181920212223void floyd(){ memcpy(d, g, sizeof d); for (int k = 0; k < n; k ++ ) for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) d[i][j] |= d[i][k] & d[k][j];}int main(){ cin >> n; for (int i = 1; i <= n; i ++ ) { int a, b; cin >> a >> ...

最短路求方案数整体思路： 首先引入拓扑序的概念：计算当前状态时，当前状态所依赖的状态都已经计算出来了 类似DP，先求出全局最小值，再分别求出每个子集中等于全局最小值的元素数量，和最短路的唯一区别是，DP是在拓扑图中做最短路，但普通的最短路中可能存在环 若将最短路的模型转化为拓扑图，则可以用类似DP的方式处理求方案数的问题 其次引入最短路树（最短路拓扑图） 概念：记录每个点是由哪个点更新来的，即若 dist[j] = dist[t] + w[i] (t -> j)，j 可由 t 更新而来。 如果没有任何限制，则可能存在权值为0的环，可以在此环上转无限次，则最短路径的方案数为 INF，相当于无解了，求不出确切的树。 所以，如果想要求最短路的方案数，则图中不能存在权值为0的环，依照上述方案记录路径，即可形成拓扑图，简单地说，将可以求最短路时可以被利用的边保存（可更新最短路径上的点的边保存），其余边去掉。 分析算法：求最短路的算法系列： 热知识：判断是否满足拓扑序，此点不能更新之前已更新的点，反之则形成环，非拓扑序 BFS系列（bfs） 一层一层扩展，保证每个点只入队一次，且只出 ...

双端队列广搜时间复杂度； 每次从队列中取出队头为 $O(1)$ 整体时间复杂度为线性的，即 $O(n + m)$ 适用场景 边权仅为0或1的图中 算法模板(整体思路类似堆优化 $dijkstra$ 算法) 12345678910111213141516171819202122232425262728void bfs(){ memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); dist[1] = 0; q.push_front(1); while(q.size()) { // 每次取出队头，时间复杂度O(1) auto t = q.front(); q.pop_front(); if(st[t]) continue; st[t] = true; for (int i = h[t]; ~i; i = ne[i]) { ...

朴素 Dijkstra 算法时间复杂度 $O(n^2)$ 算法应用情景： 不含有负权边的图中 整体思路： 初始化，将起点加入已更新的点中，并将起点的 dist 设为 0，其余点的 dist 为 INF，代表没更新 循环 n - 1 次，每次更新一个点， 用这个点更新其他点到起点的距离 如图所示： 模板代码如下：1234567891011121314151617181920212223242526272829int g[N][N]; // 邻接矩阵，存储每条边int dist[N]; // 存储1号点到每个点的最短距离bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 先选中一个点，剩余 n - 1 个点，迭代 n - 1 次 for (int i = 0; i < n - 1; i ++ ) { int t = ...

跳转到B站 测试的文章一级标题二级标题三级标题四级标题五级标题六级标题 BP算法 训练集 $\left\{\left(x^{(1)}, y^{(1)}\right), \ldots,\left(x^{(m)}, y^{(m)}\right)\right\}$ 设 $\Delta_{i j}^{(l)}=0(\text { for all } l, i, j)$ $\begin{array}{l}{\text {For } i=1 \text { to } m}\end{array}$ \begin{array}{l}{\text { Set } a^{(1)}=x^{(i)}} \\ {\text { Perform forward propagation to compute } a^{(l)} \text { for } l=2,3, \ldots, L} \\ {\text { Using } y^{(i)}, \text { compute } \delta^{(L)}=a^{(L)}-y^{(i)}} \\ {\text { Compute } \delta^{ ...

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment