错排问题，就是把书架上的n本书，重新摆放（也叫重排）生成一个新的排列，每一本书都不在它原来的位置上，问有几种方案。      我们通过排列，联想到组合数学问题，因此我们试着把它分...

     求凸包就是求一个最小周长凸多边形，使得所求点集都被包含在这个凸多边形里。    为什么是凸多边形？根据三角形不等式，如果有一个满足包含所有点的凹多边形，一定存在额外的一条边使得多边形的边...

  众所周知，dijkstra基于贪心，是不能有负边权的，而Bellman-Ford可以。来自Bellman-Ford的SPFA同样可以优秀地判负环，我们介绍几种方案：   一、朴素做法：进队n次，则不满足。 因为Bellman-Ford是通过三...

   弄懂树剖这方面各个数组的定义，并熟练掌握线段树，树链剖分就不是难事。      我弄懂树链剖分是在教练的讲解和这篇文章的帮助下理解的，除了参考那篇文章，我再把重要的部分总结一下。  ...

摸鱼思考了一上午并调了下午两节课终于出来了。      首先，区间翻转用splay来做真的是不二选择，感觉现在已经把splay磨得差不多了。这个题其实就是像线段树一样打上lazy-tag来控制时间复杂度的思想...

在网上找了一下，发现很多人都没有存父节点指针，今天实现了一下，感觉确实简洁许多。      不存父指针，有一个关键操作就是赋值，这一操作可以用=号来实现，也可以在函数调用时取址，直接更改，这里...

   上午＋下午写了3个多小时终于写完了。。。   文章背景：    昨天写了整整一下午+一晚上的AVL树还是放弃了，今天学了splay以为代码量会小一点，结果……      我们需要维护的操作有 ...

tarjan算法的大纲： tarjan专题   最主要的分为两个板块，有向图和无向图 一、有向图 1.缩点、强连通分量 代码和注释    如果在一个有向图中，任意两个节点可以互相到达，那么这些点和它们之间的边...

洛谷的这个模板题可以说是相当坑了 【P3388】【模板】割点（割顶）细节处理不到位总是拿不好分。 题目描述 给出一个n个点，m条边的无向图，求图的割点。 输入输出格式 输入格式： 第一行输入n,m 下面...

   例题是洛谷P3387缩点      顾名思义，缩点就是将等价的几个点转化为一个点，点权可累加。那么我们就要用tarjan来求一下哪些点可以缩在一起。   1.dfn和low的含义    tarjan算法有两个...