最近遇到了好多这样的题,感觉应该是一类题. 这一类问题就是要求满足某一限制条件下的最短路,比如每一条边都有两种边权,要求路径上其中一种边权之和小于某个值的条件下的另一个边权最小的路径.

查缺补漏 冲刺icpc

前缀函数

前缀函数 代表在字符串 中, 以 结尾的字串中, 最长的相等的前后缀, 即前 个字符组成的字符串和后 个字符组成的字符串是相等的.

有N个变量,每个变量都能取T或F，需要满足M个条件: or

要给每个变量赋值,满足所有条件.

构造有向图G,每个拆成两个点2i和2i+1, 分别表示取T或者F. 每个变量选其中的一个进行标记,标记了节点2i表示,标记2i+1表示.

对于每个条件,如 or ,可以从表示点i为F的节点到表示点j为F的节点连一条边,表示如果点i为F,那么点j一定是F. 同时,还要从表示点j为T的点向表示点i为T的点连一条边.

DFS方法

无向图割点/桥&双连通分量

无向图图中所有边要么是树边，要么是反向边。

割点的条件

1. 当树根有两个及以上子节点时，树根是割点。
2. 非根节点u为割点，当且仅当该点存在一个子节点v，且v及其所有后代都没有反向边连回u的祖先。（连回u不算，此时u是割点）

用LOW[x]代表x及其后代能连回祖先最小的DFN值，那么上述条件即为u存在一个子节点v，使得LOW[v] DFN[u].

另外，若v的后代最早只能连到v自己，那么边(u,v)是桥。

基础算法

贪心

根据贪心的数学背景我们在做贪心题目的时候一般有两种策略： 1.把一个问题划分成很多子问题，对于每个子问题直接求最优解，然后合成一个最优解； 2.对于当前局面，搜索所有可能的“临近局面”，选择最优的局面进行转移