第一章、图
Codeforces
246D. Colorful Graph
Codeforces 25D. Roads not only in Berland 并查集
1.3 图的遍历
Codeforces
278C. Learning Languages 图的遍历
Codeforces
103B. Cthulhu 寻找奈亚子
Codeforces
217A. Ice Skating 搜索
Codeforces
263 D. Cycle in Graph 环
Codeforces
107A. Dorm Water Supply 搜图
1.3.3 图的拓扑排序
1.3.4 图的可行遍性
欧拉回路的一点研究与Codeforces
62D Wormhouse
第二章、树
Codeforces
131D. Subway 寻找环-树的最短路径
Codeforces 61D. Eternal Victory 树的性质
2.2 图的生成树
2.2.1 最小生成树
2.2.2 次小生成树
HDU 4081 Qin Shi Huang's National Road System 最小/次小生成树的性质
UVA 10600 ACM Contest and Blackout 次小生成树/裸
2.2.3 有向图的最小树形图
2.3 树的其他问题
2.3.1 树上两点的最近公共祖先
2.3.2 树的最小支配集，最小点覆盖与最大独立集
第三章、图的最短路径问题
3.1 单源最短路径
3.1.1 Dijkstra算法
白书上的dijkstra+堆优化/dijkstra的一些性质
Uva 11374 - Airport Express 最短路
Uva
10917 - Walk Through the Forest 最短路
UVA
10816 Travel in Desert 最短路+二分
3.1.2 Bellman-Ford算法
Uva
11090 - Going in Cycle!! bellman-ford 负权环 二分
白书上的Bellman-Ford模板
poj3621
Sightseeing Cows bellman-ford 判负权环
UVA
11280 Flying to Fredericton 最短路DP
3.1.3 SPFA算法
poj 3013 Big Christmas Tree 最短路
Codeforces 144D. Missile Silos 最短路
3.2 每对顶点间的最短距离
3.2.1 Floyd算法
UVA
10269 Adventure of Super Mario floyd dp
3.3 最短路问题的扩展与应用
3.3.1 k短路
3.3.2 差分约束系统
3.3.3 DAG图上的单源最短路径
3.3.4 Floyd求最小环
第四章、连通性问题
poj
1659 Frogs' Neighborhood havel定理
4.1 图的强连通
hdu 2767 Proving Equivalences 等价性证明 强连通分量
Uva
11324 - The Largest Clique 缩点 求最大团
4.1.2 Kosaraju算法
4.1.3 Tarjan算法
4.1.4 Garbow算法
4.2 最小点基
4.2.2 最小点基
4.2.3 最小权点基
4.3 图的双连通
4.3.2 点双连通分量
Poj 3713 Transferring Sylla 3-连通
4.3.3 边双连通分量
4.4 图的全局最小割问题和Stoer-Wagner算法
4.5 2-SAT
4.5.1 SAT
4.5.1 2-SAT
POJ
3207 Ikki's Story IV - Panda's Trick 2-SAT
POJ
2723 Get Luffy Out 二分 2-SAT
poj
3683 Priest John's Busiest Day 2-SAT
第五章、网络流
5.2 最大流定理
最大流算法---Ford-Fulkson方法的基本思想与Edmond-Karp算法
nefu
473 Drainage DitchesHal Burch 最大流
nefu
476 太空飞行计划问题 最大权闭合图问题(不懂)
poj
1459 Power Network 最大流建图练习
5.3 有上下界的网络流
5.4 网络的费用流
省赛练习2
Doctor NiGONiGO’s multi-core CPU 最大费用最大流
第六章、二分图及匹配算法
6.2 匹配基本定理
6.3 二分图最大匹配
nefu
474 The Perfect StallHal Burch 二分图最大匹配
POJ
2112 Optimal Milking 二分图最大匹配+二分答案
6.4 二分图最佳匹配
6.5 二分图模型的应用
6.5.1 二分图最小点覆盖
6.5.2 有向无环图的最小路径覆盖
6.5.3 二分图的最大独立点集
6.5.4 最小点权覆盖
UVA图论练习题
0.基础练习
1.DFS及其应用
2.最短路及其应用
3.最小生成树
Minimal Spanning Tree and Variants
4.二分图
5.网络流
xczxc