图论
Template
DFS
CF——Codeforces 592 D. Super M（树的直径）
CF——Codeforces Round #428 (Div. 2)C. Journey(dfs+期望）
HDU 5877 Weak Pair(dfs +树状数组 、 树上逆元思想)
BFS
BFS
BFS （图）——Codeforces 788 C. The Great Mixing
BFS——Poj 3669 Meteor Shower
BFS_set优化扩展边(set优化）
补图求最短路 bfs + 双set优化，用上面的那个TLE了，这个写法比较保险
Tarjan
Poj 2117 Electricity(求割点）
Poj1144 Network(求割点）
强连通分量分解
- 两遍dfs O(VE)
最短路
HDU2224The shortest path(BTSP)
并查集
生成树
最小生成树
次小生成树
Poj 1679 The Unique MST 次小生成树
HDU 4081 Qin Shi Huang’s National Road System 次小生成树
最小树形图
Poj 3467 Command Network 最小树形图
HDU 2121 Ice_cream’s world II 无根最小树形图
HDU 4049 Transfer water 多根最小树形图
生成树计数
UVA - 10766 Organising the Organisation (生成树计数-补图） 基尔霍夫矩阵
URAL - 1627 Join 生成树计数模板题
树
洛谷P1268树的重量(LCA、树的的构造)
网络流
最大流最小割
EK、Dinic、SAP三种算法模板
HDU 3572 Task Schedule(建图)
HDU 5889 Barricade(最短路径上跑最小割 spfa + dicnic(当前弧优化）
HDU 1532 Drainage Ditches(入门) [最大流]
HDU 3549 Flow Problem(入门) [最大流]
洛谷 P2763 试题库问题 最大流
HDU 3572 Task Schedule 网络流 判断满流 建图
HDU 2732 Leapin’ Lizards 最大流拆点+建图
HDU 3338 Kakuro Extension 最大流 行进列出
HDU 2883 kebab 离散化 + 最大流 判断满流
HDU 3605 Escape 最大流 二进制并点建图
HDU 4240 Route Redundancy 求一条（流最大）的路径
HDU 3081 Marriage Match II 最大流 之 二分图匹配 + 二分
HDU 3277 Marriage Match III 最大流 + 二分 + 并查集 + 拆点建图
HDU 3416 Marriage Match IV 最短路跑路径 + 最大流
洛谷 P2765 魔术球问题 最大流 解决最小路径覆盖问题
洛谷 P2774 方格取数问题 建图 最大取和= 最大和-最小舍弃和 = 最小割 = 最大流
洛谷 P2766 最长不下降子序列问题 最大流 分层建图
最小费用最大流
mcf-spfa 模板
HDU 1533 Going Home 最小费用最大流基础题
HDU 3488 Tour 有向环最小权值覆盖 最小费用最大流
HDU 3667 Transportation 最小费用最大流 平方扩边
HDU 4411 Arrest 费用流之可行流
青岛区域赛 Finding Hotels 最小费用流概率建图
上下界网络流
ZOJ 2314 Reactor Cooling (上下界无源汇可行流)
POJ 2396 Budget (上下界有源汇可行流)
ZOJ 3229 Shoot the Bullet (上下界有源汇最大流)
HDU 3157 Crazy Circuits （上下界有源汇最小流）
最大权闭合子图
洛谷 P2805 [NOI2009]植物大战僵尸 网络流 - 最大权闭合子图
二分图
Template
二分图匹配 判断是否为二分图 —— 模板
二分图匹配 Hopcroft-Carp算法——模板
二分图匹配匈牙利算法——模板
二分图
HDU5737 Necklace
HDU2389 Rain on your Parade
洛谷P1525 关押罪犯(二分+二分图染色)
