信息学奥赛一本通提高篇 第三章 图论

题单介绍

**因为洛谷没有书上的全套题目,所以此题单仅收藏了部分例题+课后习题。如果有所遗漏,欢迎私信补充。** 【模板】最小生成树 不用解释,例题。 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] 原始生物