Void Space

发表于 更新于 分类于

差分约束

最长路径

新问题：如何求最长路径？

1、Dijkstra按最短路的方法直接去求最长路？ 思考：为何不可以？ 思考：转换成负权求最短路？（Dij算法的软肋）

2、常见方案： Floyd算法求每对节点之间的最长路经 （因为最长路径也满足最优子结构性质，而Floyd算法的实质就是动态规划）

阅读全文 »

发表于 更新于 分类于

最短路进阶

回顾

  • 按照最短路径的长度递增的次序，依次求得——源点到其余各点的最短路径！
  • 先求——最短的那条最短路径（特点？）
  • 再求——第二短的最短路径（特点？）
  • ……
  • 依次类推（特点？）
  • ……
  • 最终求出所有的最短路径
阅读全文 »

发表于 更新于 分类于

倍增算法

关联复习-树链剖分

树链剖分的应用场景？ （树的路径操作、子树的操作）

LCA（Least Common Ancestors），即最近公共祖先。 是指这样一个问题：在有根树中，找出某两个结点u和v最近的公共祖先（另一种说法，离树根最远的公共祖先）。

RMQ

关于RMQ问题

RMQ（Range Minimum/Maximum Query），即区间最值查询。是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中指定区间[i，j]中的最大/小值。

LCA问题和RMQ问题的关系？

LCA《-》RMQ可以互相转换

阅读全文 »

发表于 更新于 分类于

树链剖分 轻重链剖分

树链剖分即轻重链剖分，两者是一个概念

轻重链剖分

树链剖分 - 轻重链剖分

  • 将树剖成一条条不相交的从祖先到子孙的链。

  • 设\(\text{size}[x]\)表示\(x\)点的子树大小， \(\text{size}[x] = 1 + \text{sum}(\text{size}[y])\)，其中\(y\)是\(x\)的儿子。

  • 对于每个点\(x\)，将儿子中\(\text{size}\)最大的那个儿子作为它的重儿子，剩下的作为轻儿子。

    阅读全文 »

发表于 更新于 分类于

2-SAT

SAT 问题定义

SAT的全称：satisfiability（可满足性）

有一个由N个布尔值组成的序列A，给出一些限制关系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0..N-1]的值，使得其满足所有限制关系，这就是SAT问题。

2-SAT 特殊点

特别的，若每种限制关系中最多只对两个元素进行限制，则称为2-SAT问题。

2-SAT问题是有多项式解法的，而3-SAT就是npc问题。

阅读全文 »

发表于 更新于 分类于

强连通分量

例题一

  • 给定一个有向图，统计有多少点对u, v(u<v)满足： u可以到达v，且v可以到达u。

  • 思考：如何解决？

  • 暴力？复杂度不可想象…

强连通分量定义

在一个有向图中，选取一个点集S，如果对于S中的任意两点u, v都满足u可以到达v，则称S是强连通的。

如果一个强连通点集S中，不能再加入更多的点使得它仍然强连通，则称S是强连通分量。

阅读全文 »

发表于 更新于 分类于

区间 DP

DP回顾

DP三个特征（基本条件）：

  • 重叠子问题
  • 最优子结构
  • 无后效性

重叠子问题：就是影响到前面的
最优子结构：局部是最优的，北京到上海是北京到杭州的子结构
无后效性：大不影响小

思考：DP和搜索的区别？

引导题目

阅读全文 »
0%