图论 学习清单

图论 学习清单

一、最短路

最短路图
最短路树

题目：

• [USACO09JAN]安全出行Safe Travel
• [FJOI2014]最短路径树问题

二、最小生成树

题目：

• [HNOI2006]公路修建问题
• [JSOI2008]最小生成树计数

三、LCA

题目：

• bzoj3712 Fiolki
• [NOIP2016]天天爱跑步

四、差分约束

题目：

• [HNOI2005]狡猾的商人

五、强联通分量

题目：

• [HAOI2010]软件安装
• UVA1364 Knights of the Round Table

六、二分图

内容：

• 二分图染色
• 二分图匹配（匈牙利算法）；
• 二分图最小点覆盖
• 二分图最小路径覆盖
• 二分图最大独立集
• DAG的最小不相交路径覆盖

题目：

• [NOIP2008]二栈排序