0x6B 总结与练习

本章内容把图论的知识点划分为6个板块进行了讲解：最短路、最小生成树、树结构相关的图论问题、图连通性、二分图、网络流。前3个板块是图论中的基础内容，后3个板块则在难度与综合性上都有所提升。图论的知识脉络不像DP那样逐层递进，而是具有广泛、分散的特点。在各式各样的图论算法和模型基础上，还存在许多变种。因为篇幅有限，无法逐一展开，读者在回顾本章知识点时，不妨尝试主动把问题进行变形，争取能够举一反三，独立思考出解决方案。

本章知识点

最短路

图的基本概念，图的邻接矩阵与邻接表存储

单源最短路径问题，Dijkstra算法及堆优化，Bellman-Ford，SPFA算法

单源最短路径各算法的适用范围，单源最短路径问题的变形与扩展

任意两点间最短路径问题，Floyd算法的本质及应用

传递闭包，无向图最小环问题

最小生成树

最小生成树的定义与基本性质，Kruskal 算法，Prim 算法

最小生成树问题的变形与扩展

树的直径与最近公共祖先

树的直径的定义与计算：动态规划或两次BFS

树的直径的性质与应用，尤其是直径的“最长性”

LCA的定义与计算，向上标记法，树上倍增法，LCA的Tarjan算法

LCA的扩展与应用：“树上差分算法”等

树上倍增法的应用：“次小生成树”等

基环树

基环树、外向树、内向树的定义，基环树的处理方法

负环与差分约束

最短路中负环的判定方法

差分约束系统的求解，差分约束到最短路的转化

Tarjan算法与无向图连通性

无向图的搜索树、时间戳与追溯值，割点与割边判定法则
Tarjan算法求割点、割边、点双连通分量、边双连通分量
双连通分量的性质与应用，缩点
欧拉图的判定，欧拉路的计算

Tarjan算法与有向图连通性
有向图的搜索树、边的分类，Tarjan算法求强连通分量
强连通分量的性质与应用，缩点
有向无环图的必经点与必经边，路径条数取模法
2-SAT问题的判定，自底向上拓扑排序构造方案

二分图的匹配

二分图的判定：染色法判断是否存在奇环

二分图最大匹配：匈牙利（增广路）算法

二分图匹配的模型构建方法，“0要素”与“1要素”，二分图多重匹配

二分图带权最大匹配：KM算法

二分图的覆盖与独立集

二分图最小点覆盖，模型构建的“2要素”

二分图最大独立集，“团”与独立集的对应关系，补图转化思想有向无环图的最小路径点覆盖、最小路径可重复点覆盖

网络流初步

网络流的定义，“容量限制”“斜对称”“流量守恒”三条基本定律最大流的Edmonds-Karp增广路算法与Dinic算法网络流求解二分图匹配的方法，二分图最大匹配的必须边、可行边判最小割的定义，最大流最小割定理，“点边转化”技巧费用流的Edmonds-Karp增广路算法及其应用

$\spadesuit$ 练习

完成本章中所有例题的代码实现（标有*的题目选做）
Sightseeing

题目地址：POJ3463，提示：最短路/单源次短路及其条数

3.升降梯上

题目地址：TYVJ2032，提示：最短路/节点扩展到二维

4.GF和猫咪的玩具.

题目地址：TYVJ1423，提示：最短路/任意两点间最短路

5. 社交网络

题目地址：NOI2007/BZOJ1491，提示：最短路/任意两点间最短路及其条数

6. Arctic Network

题目地址：POJ2349，提示：最小生成树

7.*四叶草魔杖

题目地址：TYVJ2054，提示：最小生成树/状态压缩动态规划

8. 直径

题目地址：BZOJ3124，提示：树的直径的必须边

9. 逃学的小孩

题目地址：NOI2003/BZOJ1509，提示：树的直径

10. 聚会

题目地址：BZOJ1832/BZOJ1787，提示：最近公共祖先

11. Rendezvous

题目地址：BZOJ2791，提示：基环树/最近公共祖先

12. Cashier Employment

题目地址：POJ1275，提示：差分约束

13.*最优高铁环

题目地址：TYVJ1706，提示：负环判定/01分数规划

14. Redundant Paths

题目地址：POJ3177/BZOJ1718，提示：Tarjan算法/桥

15. *矿场搭建

题目地址：BZOJ2730，提示：Tarjan算法/割点

16.逃不掉的路

题目地址：ContestHunter#24-C，提示：边双连通分量/缩点/无向图必经边

17. Traffic Real Time Query System

题目地址：HDOJ3686，提示：点双连通分量/缩点/无向图必经点

18. John's trip

题目地址：POJ1041，提示：欧拉路

19. 太鼓达人

题目地址：BZOJ3033，提示：欧拉路

20. Going from u to v or from v to u

题目地址：POJ2762，提示：强连通分量/缩点

21.*杀人游戏

题目地址：BZOJ2438，提示：强连通分量/缩点
22. Planet

题目地址：BZOJ1997，提示：2-SAT
23. Wedding
题目地址：POJ3648，提示：2-SAT/输出方案
24. Team Them Up!
题目地址：POJ1112，提示：二分图判定/动态规划
25. Place the Robots
题目地址：ZOJ1654，提示：二分图最大匹配
26. Steady Cow Assignment
题目地址：POJ3189，提示：二分图多重匹配
27. Going Home
题目地址：POJ2195，提示：二分图带权匹配
28. Air Raid
题目地址：POJ1622，提示：二分图最小路径点覆盖
29. Sorting Slide
题目地址：POJ1486，提示：二分图最大匹配的必须边
30. King's Quest
题目地址：POJ1904，提示：二分图最大匹配的可行边
31. Drainage Ditches
题目地址：POJ1273，提示：最大流

0x6B_总结与练习