信息学奥赛一本通提高篇 第三章 图论
题单介绍
**因为洛谷没有书上的全套题目,所以此题单仅收藏了部分例题+课后习题。如果有所遗漏,欢迎私信补充。**
【模板】最小生成树 不用解释,例题。
P4180、P4208 是最小生成树的部分题目~~不要问我为什么这么难,因为我只能找到这些了QAQ~~
两个【模板】单源最短路径 不用解释,最短路径的例题qwq
P6175 是最小环模板。
P4011~P3008 是最短路径章节的部分题目。
P5530~P3385 是SPFA~~已死算法~~优化的部分题目。
P5960~P4878 是差分约束系统的部分题目。
P3387~P5782 是强连通分量(缩点)的部分题目。
P3388~P3469 是割点(桥)的部分题目。
P2731~P5921 是欧拉回路的部分题目。
题目列表
【模板】最小生成树
[BJWC2010] 严格次小生成树
[JSOI2008] 最小生成树计数
【模板】单源最短路径(弱化版)
【模板】单源最短路径(标准版)
无向图的最小环问题
孤岛营救问题
[USACO07FEB] Cow Party S
[USACO06NOV] Roadblocks G
最短路计数
[CQOI2005] 新年好
[NOIP 2009 提高组] 最优贸易
汽车加油行驶问题
[USACO11JAN] Roads and Planes G
[BalticOI 2002] 双调路径
[HNOI2009] 最小圈
[USACO06DEC] Wormholes G
【模板】负环
【模板】差分约束
INTERVAL - Intervals
[SCOI2011] 糖果
[USACO05DEC] Layout G
【模板】缩点
[USACO03FALL / HAOI2006] 受欢迎的牛 G
[ZJOI2007] 最大半连通子图
间谍网络
[APIO2009] 抢掠计划
[POI 2001] 和平委员会
【模板】割点(割顶)
[USACO06JAN] Redundant Paths G
[HNOI2012] 矿场搭建
[ZJOI2004] 嗅探器
[POI 2008] BLO-Blockade
[USACO3.3] 骑马修栅栏 Riding the Fences
John's trip
[POI 1999 R3] 原始生物