tarjan

一句话思路我们求割点和割边,只要知道其子节点能否通过不经过其父节点(割点)或父节点所在的边(割边)到达父节点的祖先节点的位置即可。     阅读全文
nodeee 8月28日
0 评论

【未完待续】基础博弈论

Nim博弈题意简述有n堆棋子,每一次可以从一堆中取走不少于1的任意个棋子。不能取的一方输。问先手是否必胜。(所有博弈的前提是两者都采取最优策略)定理设第i...     阅读全文
nodeee 1月27日
0 评论

浅谈K短路

关于K短路理解很难,但是懂了之后真的发现很简单。主要是大家脑海里没有一个正确的运行的图。大家要想出是如何跑的就行。前置知识:一次反向最短路(其他都算不上知...     阅读全文
nodeee 1月26日
3 评论

浅谈最大流:EK和dinic

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

逆序对

简介查找一个序列中的逆序对个数。逆序对:如果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 评论