搜索结果
查询Tags标签： 分量，共有 25条记录-
tarjan算法求强连通分量<模板>
上次发的时候不小心被我设置成了只有自己可见，今天补上 dfn[now]表示在now点在dfs搜索树中的dfs序。 low[now]表示的是now通过后向边、横叉边能到达的dfn最小的点的dfs序。 我们取一个强连通分量中dfn最小的点作为整个强连通分量的代表元素。 因此low[now]的实际意义就是…
2021/8/22 17:06:12 人评论 次浏览 -
tarjan算法求强连通分量<模板>
上次发的时候不小心被我设置成了只有自己可见，今天补上 dfn[now]表示在now点在dfs搜索树中的dfs序。 low[now]表示的是now通过后向边、横叉边能到达的dfn最小的点的dfs序。 我们取一个强连通分量中dfn最小的点作为整个强连通分量的代表元素。 因此low[now]的实际意义就是…
2021/8/22 17:06:12 人评论 次浏览 -
AcWing 368. 银河
原本是一个差分约束的问题，但是由于数据过大可能导致\(spfa\)被卡，而由于这道题的边权只有\(0，1\)两种，比较特殊，所以使用\(tarjan\)求连通分量，缩点，递推的方式也能完成，时间复杂度是线性的。 用差分约束的思路根据不等式建图，然后从\(0\)号节点开始求单源最长路…
2021/7/27 23:11:10 人评论 次浏览 -
AcWing 368. 银河
原本是一个差分约束的问题，但是由于数据过大可能导致\(spfa\)被卡，而由于这道题的边权只有\(0，1\)两种，比较特殊，所以使用\(tarjan\)求连通分量，缩点，递推的方式也能完成，时间复杂度是线性的。 用差分约束的思路根据不等式建图，然后从\(0\)号节点开始求单源最长路…
2021/7/27 23:11:10 人评论 次浏览 -
数字水印算法
任务背景及简介随着互联网的普及和数字技术的广泛应用，信息媒体的数字化极大地提高了信息的存取效率, Intenet 的普及又为数字信息在世界范围内的迅速传递开辟了便捷的途径，数字产品变得极大丰富并且传播便捷，但与此同时版权保护问题也日益突出。传统的信息安全技术在数…
2021/6/26 20:27:52 人评论 次浏览 -
克鲁斯卡尔（Kruskal）算法
概览相比于普里姆算法（Prim算法），克鲁斯卡尔算法直接以边为目标去构建最小生成树。从按权值由小到大排好序的边集合{E}中逐个寻找权值最小的边来构建最小生成树，只要构建时，不会形成环路即可保证当边集合{E}中的边都被尝试了过后所形成的树为最小生成树。定义假设G=(…
2021/5/17 20:29:22 人评论 次浏览 -
数字水印 改进的patchwork算法 实现
一、算法原理 1、参考论文 甘霖,杨榆.基于变换域的Patchwork水印改进算法[J].成都信息工程大学学报,2017,32(06):623-627. 2、理论基础 （1）离散余弦变换 在水印算法中引入图像的变换域用于嵌入水印，以此增强水印的透明性。 （2）人类视觉系统特性 人类的视觉系统对不同…
2021/5/5 12:25:48 人评论 次浏览 -
音视频入门之YUV颜色编码
YUV，是一种颜色编码方法。常使用在各个影像处理组件中。YUV在对照片或视频编码时，考虑到人类的感知能力，允许降低色度的带宽。比如移动端Camera拍照捕获的图像数据、直播推流的流数据都是用这种编码格式。 Y”表示明亮度（Luminance、Luma），“U”和“V”则是色度、浓…
2021/5/4 18:26:59 人评论 次浏览 -
傅里叶变换
设对满足迪利克雷条件（绝对可积、周期内有限起伏、周期内有限间断点）的连续时间信号 \(x(t)\) 的傅立叶变换为 \(X(\omega)\)，即 \(x(t) \leftrightarrow X(\omega)\)，则 \[X(\omega)=\int_{-\infty}^{\infty} \frac {x(t)} {e^{j\omega t}} dt, \quad x(t)=\frac {1}…
2021/4/30 10:55:16 人评论 次浏览 -
有向图强连通分量的Tarjan算法
https://byvoid.com/zhs/blog/scc-tarjan/ 在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected componen…
2021/4/29 22:26:35 人评论 次浏览
