浅谈最大流:EK和dinic

问:为什么不写预流推进?答:我不会正文开始:最大流是什么网络流是求出在一个网络内从s点到t点的最大流量的算法。题目中告诉你s点(起始点),t点(结束点),...     阅读全文
nodeee 2019年12月02日
0 评论

逆序对

简介查找一个序列中的逆序对个数。逆序对:如果i<j&&a[i]>a[j]则为一对逆序对。朴素算法暴力枚举每两个数并进行比较,如果符合i<...     阅读全文
nodeee 2019年11月07日
0 评论

排序算法

快速排序快速排序是以分治(分而治之)为基本思想。分治就是把一个大问题分成多个子问题逐个解决并最终合并。1.从所有元素中选出任意一个数字作为基准数。2.找出...     阅读全文
nodeee 2019年10月28日
0 评论

二分图匹配——匈牙利算法

题目链接:P3386 【模板】二分图匹配什么是二分图?二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互...     阅读全文
nodeee 2019年10月21日
0 评论

拓扑排序&车站分级

拓扑排序使用范围在不存在互相指向的节点的有向图中。如何操作入度与出度一个点的入度记录的是指向这个点的其他节点的数量一个点的出度记录的是这个点指向的点的数...     阅读全文
nodeee 2019年10月03日
0 评论

【算法】最小环

又写了一篇博客嘿嘿~没想到吧?最小环是什么?最小环是求一个图中最小的环(说了和白说一样)Dij求法每一次除去一条边(u,v)然后再求u到v的最短路径时间复...     阅读全文
nodeee 2019年09月28日
2 评论

欧拉函数

欧拉定理$$ a^{\varphi(m)} \equiv 1 \pmod{m} $$扩展欧拉定理$$ a^b\equiv \begin{cases} a^...     阅读全文
nodeee 2019年08月28日
0 评论

最小生成树

算法目标最小生成树是找出一个图中总边权最小的那棵树的算法。在其中分为Prim和Kruskal两种算法。经典例题:浇地Prim先选任意节点为树的根节点,然后...     阅读全文
nodeee 2019年08月14日
0 评论

manacher算法

算法用途在O(n)的时间判断最长回文子串。算法思想由于我们不想当母串字符个数为偶数和母串为奇数时分别写一个程序,所以我们将这个串的字符个数强行变成奇数个。...     阅读全文
nodeee 2019年07月25日
0 评论

KMP 字符串匹配

算法思路现在有s1,s2两个字符串,其中s2是短串,s1是长串。试问s2是否是s1的字串?朴素算法:设s1长度为n,s2长度为m。s2字符串首位从s1字符...     阅读全文
nodeee 2019年07月24日
0 评论

最短Hamilton路径

题面描述给定一张 $n$ 个点的带权无向图,点从 $0$ 到 $n-1$ 标号,求起点 $0$ 到终点 $n-1$ 的最短Hamilton路径。Hamil...     阅读全文
nodeee 2019年07月23日
0 评论

线段树

线段树的构成线段树中每一个节点都是其父节点的左一半或右一半,如果是奇数除不尽的话,中间的那个数归于左一半。并且其中父节点的子子节点编号永远都是父节点的编...     阅读全文
nodeee 2019年07月20日
0 评论