《算法竞赛进阶指南》0x60图论！~~~~~

题单介绍

# 《算法竞赛进阶指南》0x60图论 ### 0x61 最短路 - Telephone Lines 【USACO 2008 JAN / AcWing 340 / [Luogu P1948](https://www.luogu.com.cn/problem/P1948)】 - 最优贸易 【CCF NOIP 2009 / AcWing 341 / [Luogu P1073](https://www.luogu.com.cn/problem/P1073)】 - 道路与航线 【USACO 2011 JAN / AcWing 342 / [Luogu P3008](https://www.luogu.com.cn/problem/P3008)】 - Sorting It All Out 【ICPC ECNA 2001 / AcWing 343 / [Luogu P1347](https://www.luogu.com.cn/problem/P1347)】 - Sightseeing trip 【CEOI 1999 / AcWing 344 / [Luogu P6175](https://www.luogu.com.cn/problem/P6175)】 - Cow Relays 【USACO 2007 NOV / AcWing 345 / [Luogu P2886](https://www.luogu.com.cn/problem/P2886)】 ### 0x62 最小生成树 - 走廊泼水节 【[AcWing 346](https://www.acwing.com/problem/content/348/)】 - Picnic Planning 【ICPC ECNA 2000 / AcWing 347 / [UVA 1537](https://www.luogu.com.cn/problem/UVA1537)】 - 最优比率生成树 【ICPC BJ 2005 / [AcWing 348](https://www.acwing.com/problem/content/350/)】 - 黑暗城堡 【Nescafe 2 / [AcWing 349](https://www.acwing.com/problem/content/351/)】 ### 0x63 树的直径与最近公共祖先 - 巡逻 【APIO 2010 / AcWing 350 / [Luogu P3629](https://www.luogu.com.cn/problem/P3629)】 - 树网的核 【CCF NOIP 2007 / AcWing 351 / [Luogu P1099](https://www.luogu.com.cn/problem/P1099)】 - 闇の連鎖 【Nescafe 14 / [AcWing 352](https://www.acwing.com/problem/content/354/)】 - 雨天的尾巴 【Vani有约会 / AcWing 353 / [Luogu P4556](https://www.luogu.com.cn/problem/P4556)】 - 天天爱跑步 【CCF NOIP 2016 / AcWing 354 / [Luogu P1600](https://www.luogu.com.cn/problem/P1600)】 - 异象石 【Adera 9 / [AcWing 355](https://www.acwing.com/problem/content/357/)】 - 次小生成树 【BJWC 2010 / AcWing 356 / [Luogu P4180](https://www.luogu.com.cn/problem/P4180)】 - 疫情控制 【CCF NOIP 2012 / AcWing 357 / [Luogu P1084](https://www.luogu.com.cn/problem/P1084)】 ### 0x64 基环树 - 岛屿 【IOI 2008 / AcWing 358 / [Luogu P4381](https://www.luogu.com.cn/problem/P4381)】 - 创世纪 【Nescafe 8 / [AcWing 359](https://www.acwing.com/problem/content/361/)】 - Freda 的传呼机 【Nescafe 26 / [AcWing 360](https://www.acwing.com/problem/content/362/)】 ### 0x65 负环与差分约束 - Sightseeing Cows 【USACO 2007 DEC / AcWing 361 / [Luogu P2868](https://www.luogu.com.cn/problem/P2868)】 - Intervals 【ICPC SWERC 2002 / AcWing 362 / [UVA 1723](https://www.luogu.com.cn/problem/UVA1723)】 ### 0x66 Tarjan 算法与无向图连通性 - BLO 【POI 2008 / AcWing 363 / [Luogu P3469](https://www.luogu.com.cn/problem/P3469)】 - Network 【ICPC Hefei 2008 pre / [AcWing 364](https://www.acwing.com/problem/content/366/)】 - Knights of the Round Table 【ICPC CERC 2005 / AcWing 365 / [SPOJ 2878](https://www.luogu.com.cn/problem/SP2878)】 - Watchcow 【USACO 2005 JAN / AcWing 366 / [Luogu P6066](https://www.luogu.com.cn/problem/P6066)】 ### 0x67 Tarjan 算法与有向图连通性 - Network of Schools 【IOI 1996 / AcWing 367 / [Luogu P2746](https://www.luogu.com.cn/problem/P2746)】 - 银河 【Nescafe 16 / [AcWing 368](https://www.acwing.com/problem/content/370/)】 - PKU ACM Team\`s Excursion 【PKU / [AcWing 369](https://www.acwing.com/problem/content/371/)】 - Katu Puzzle 【PKU / [AcWing 370](https://www.acwing.com/problem/content/372/)】 - Priest John\`s Busiest Day 【PKU / [AcWing 371](https://www.acwing.com/problem/content/373/)】 ### 0x68 二分图的匹配 - 关押罪犯 【CCF NOIP 2010 / AcWing 257 / [Luogu P1525](https://www.luogu.com.cn/problem/P1525)】 - 棋盘覆盖 【[AcWing 372](https://www.acwing.com/problem/content/374/)】 - 車的放置 【[AcWing 373](https://www.acwing.com/problem/content/375/)】 - 导弹防御塔 【Nescafe 19 / [AcWing 374](https://www.acwing.com/problem/content/376/)】 - Ants 【ICPC NEERC 2007 / AcWing 375 / [UVA 1411](https://www.luogu.com.cn/problem/UVA1411)】 ### 0x69 二分图的覆盖与独立集 - Machine Schedule 【ICPC BJ 2002 / AcWing 376 / [UVA 1194](https://www.luogu.com.cn/problem/UVA1194)】 - Muddy Fields 【USACO 2005 JAN / AcWing 377 / [Luogu P6062](https://www.luogu.com.cn/problem/P6062)】 - 骑士放置 【[AcWing 378](https://www.acwing.com/problem/content/380/) / [Luogu P3355（数据更强）](https://www.luogu.com.cn/problem/P3355)】 - Vani 和 Cl2 捉迷藏 【Violet 4 / Nescafe 21 / CCF CTSC 2008 / [AcWing 379](https://www.acwing.com/problem/content/381/)】 ### 0x6A 网络流初步 - 舞动的夜晚 【CHR #17 / [AcWing 380](https://www.acwing.com/problem/content/382/)】 - Cable TV Network 【ICPC SEERC 2004 / AcWing 381 / [UVA 1660](https://www.luogu.com.cn/problem/UVA1660)】 - K 取方格数 【PKU / AcWing 382 / [Luogu P2045](https://www.luogu.com.cn/problem/P2045)】 ### 0x6B 总结与练习 - Sightseeing 【BAPC 2006 QI / [AcWing 383](https://www.acwing.com/problem/content/385/)】 - 升降梯上 【Nescafe 28 / [AcWing 384](https://www.acwing.com/problem/content/386/)】 - GF 和猫咪的玩具 【[AcWing 385](https://www.acwing.com/problem/content/387/)】 - 社交网络 【CCF NOI 2007 / AcWing 386 / [Luogu P2047](https://www.luogu.com.cn/problem/P2047)】 - Arctic Network 【ICPC Waterloo 2002 / AcWing 387 / [UVA 10369](https://www.luogu.com.cn/problem/UVA10369)】 - 四叶草魔杖 【Nescafe 29 / [AcWing 388](https://www.acwing.com/problem/content/390/)】 - 直径 【SDOI 2013 / AcWing 389 / [Luogu P3304](https://www.luogu.com.cn/problem/P3304)】 - 逃学的小孩 【CCF NOI 2003 / AcWing 390 / [Luogu P4408](https://www.luogu.com.cn/problem/P4408)】 - 聚会 【AHOI 2008 / AcWing 391 / [Luogu P4281](https://www.luogu.com.cn/problem/P4281)】 - Rendezvous 【POI 2012 / AcWing 392 / [Luogu P3533](https://www.luogu.com.cn/problem/P3533)】 - Cashier Employment 【ICPC Tehran 2000 / [AcWing 393](https://www.acwing.com/problem/content/395/)】 - 最优高铁环 【[AcWing 394](https://www.acwing.com/problem/content/396/)】 - Redundant Paths 【USACO 2006 JAN / AcWing 395 / [Luogu P2860](https://www.luogu.com.cn/problem/P2860)】 - 矿场搭建 【HNOI 2012 / AcWing 396 / [Luogu P3225](https://www.luogu.com.cn/problem/P3225)】 - 逃不掉的路 【CHR #24 / [AcWing 397](https://www.acwing.com/problem/content/399/)】 - Traffic Real Time Query System 【ICPC Hefei 2010 / AcWing 398 / [UVA 1464](https://www.luogu.com.cn/problem/UVA1464)】 - John\`s trip 【ICPC CERC 1995 / AcWing 399 / [UVA 302](https://www.luogu.com.cn/problem/UVA302)】 - 太鼓达人 【Nescafe 18 / [AcWing 400](https://www.acwing.com/problem/content/402/)】 - Going from u to v or from v to u 【PKU / [AcWing 401](https://www.acwing.com/problem/content/403/)】 - 杀人游戏 【中山市选 2011 / AcWing 402 / [Luogu P4819](https://www.luogu.com.cn/problem/P4819)】 - Planar 【HNOI 2010 / AcWing 403 / [Luogu P3209](https://www.luogu.com.cn/problem/P3209)】 - Wedding 【ICPC Waterloo 2007 / AcWing 404 / [UVA 11294](https://www.luogu.com.cn/problem/UVA11294)】 - Team Them Up! 【ICPC NEERC 2001 / AcWing 405 / [UVA 1627](https://www.luogu.com.cn/problem/UVA1627)】 - Place the Robots 【ZJU / [AcWing 406](https://www.acwing.com/problem/content/408/)】 - Steady Cow Assignment 【USACO 2006 FEB / AcWing 407 / [Luogu P2857](https://www.luogu.com.cn/problem/P2857)】 - Going Home 【ICPC PacificNW 2004 / [AcWing 408](https://www.acwing.com/problem/content/410/)】 - Air Raid 【ICPC Asia Dhaka 2002 / AcWing 409 / [UVA 1184](https://www.luogu.com.cn/problem/UVA1184)】 - Sorting Slide 【ICPC SWERC 1998 / AcWing 410 / [UVA 663](https://www.luogu.com.cn/problem/UVA663)】 - King\`s Quest 【ICPC NEERC 2003 / AcWing 411 / [UVA 1327](https://www.luogu.com.cn/problem/UVA1327)】 - Drainage Ditches 【USACO Section 4 / AcWing 412 / [Luogu P2740](https://www.luogu.com.cn/problem/P2740)】

题目列表

  • [USACO08JAN] Telephone Lines S
  • [NOIP2009 提高组] 最优贸易
  • [USACO11JAN] Roads and Planes G
  • 排序
  • 无向图的最小环问题
  • [USACO07NOV] Cow Relays G
  • Picnic Planning
  • [APIO2010] 巡逻
  • [NOIP2007 提高组] 树网的核
  • [Vani有约会] 雨天的尾巴 /【模板】线段树合并
  • [NOIP2016 提高组] 天天爱跑步
  • [BJWC2010] 严格次小生成树
  • [NOIP2012 提高组] 疫情控制
  • [IOI2008] Island
  • [USACO07DEC] Sightseeing Cows G
  • Intervals
  • [POI2008] BLO-Blockade
  • KNIGHTS - Knights of the Round Table
  • [USACO05JAN] Watchcow S
  • [USACO5.3] 校园网Network of Schools
  • [NOIP2010 提高组] 关押罪犯
  • Ants
  • Machine Schedule
  • [USACO05JAN] Muddy Fields G
  • 骑士共存问题
  • 电视网络 Cable TV Network
  • 方格取数加强版
  • [NOI2007] 社交网络
  • Arctic Network
  • [SDOI2013] 直径
  • [NOI2003] 逃学的小孩
  • [AHOI2008] 紧急集合 / 聚会
  • [POI2012] RAN-Rendezvous
  • [USACO06JAN] Redundant Paths G
  • [HNOI2012] 矿场搭建
  • Traffic Real Time Query System
  • John's trip
  • [中山市选] 杀人游戏
  • [HNOI2010] 平面图判定
  • Wedding
  • 团队分组 Team them up!
  • [USACO06FEB] Steady Cow Assignment G
  • Air Raid
  • Sorting Slides
  • King's Quest
  • [USACO4.2] 草地排水Drainage Ditches