经典问题

稳定匹配及其推广/二分匹配 G-S算法和推广
区间调度/带权值的区间调度/多资源区间调度/延迟区间调度/其他推广
独立集

图&树

存储方式：邻接矩阵 or 邻接表
有向图才有强连通性
DAG才有拓扑排序
图的最短路径：
1. dijkstra（正边贪心思想）普通时间复杂度需要 O（mn）进行改进，使用优先队列的数据结构存储图，可以将其降至O（mlogn）
2. Bellman和Ford（存在负边动态规划）
最小生成树
1. kruskal：从一个起点发散，逐步添加当前最小的边长
- 整个过程是逐步合并不同的点集，运用并差集（union-find）数据结构可以将实现过程变简单
- 并差集用固定数组实现，会让合并的时间较长，故最好用链表实现。
- 并查集至少支持3种操作：初始化集合，查找元素所属集合，合并两个集合。
- 延伸问题，如果边权值并非互不相同，能否用kruskal法找到所有最小生成树。
1. prim：逐步将整个图中的最小边长添加到集合中
2. 逆向删除法：逐步从整张图删除最大的边长，并保持连通性。
~~最优有向树/最小费用有向树~~
霍夫曼编码和数据压缩