【后期专题】图论
【后期专题】图论
章节 5. 最短路综合应用
重力球和冰原探险可以放一放，挑一个阳光明媚头脑清晰的好日子来写。
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P1993 小 K 的农场 | 86 | 19 | 6 |
| P1462 通往奥格瑞玛的道路 | 65 | 14 | 6 |
| P7473 [NOI Online 2021 入门组] 重力球 | 6 | 1 | 7 |
| P3716 [CTSC2000] 冰原探险 | 20 | 5 | 7 |
| P3953 [NOIP 2017 提高组] 逛公园 | 22 | 3 | 7 |
| P1119 灾后重建 | 26 | 15 | 6 |
| P3403 跳楼机 | 22 | 12 | 7 |
| P1073 [NOIP 2009 提高组] 最优贸易 | 40 | 17 | 6 |
| P9751 [CSP-J 2023] 旅游巴士 | 43 | 11 | 6 |
| P4568 [JLOI2011] 飞行路线 | 19 | 9 | 6 |
| P2865 [USACO06NOV] Roadblocks G | 29 | 8 | 7 |
| P3956 [NOIP 2017 普及组] 棋盘 | 4 | 3 | 6 |
| P1629 邮递员送信 | 15 | 9 | 5 |
| D0444 旅游 | 4 | 4 | 10 |
章节 6. 最小生成树
还有上面说明的 ABC282E、ABC401E。这里有不少无聊的题，或者说放在了这个章节后就无聊的题。没学 LCA 之前的 Kruskal 还是比较无聊的，随便写写吧。
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P3366 【模板】最小生成树 | 122 | 35 | 5 |
| P4047 [JSOI2010] 部落划分 | 36 | 24 | 6 |
| P10928 走廊泼水节 | 36 | 25 | 6 |
| T1348 【例4-9】城市公交网建设问题 | 96 | 42 | 4 |
| T1350 【例4-11】最短网络(agrinet) | 71 | 42 | 2 |
| T1391 局域网(net) | 59 | 42 | 1 |
| T1393 联络员(liaison) | 87 | 39 | 4 |
| T1394 连接格点(grid) | 75 | 31 | 5 |
| P1265 公路修建 | 37 | 11 | 6 |
| P2323 [HNOI2006] 公路修建问题 | 18 | 10 | 6 |
| P1396 营救 | 30 | 15 | 5 |
| P1550 [USACO08OCT] Watering Hole G | 34 | 17 | 5 |
| P1195 口袋的天空 | 36 | 17 | 5 |
| P1194 买礼物 | 39 | 16 | 5 |
| P4951 [USACO01OPEN] Earthquake | 21 | 13 | 7 |
| P2573 [SCOI2012] 滑雪 | 41 | 15 | 7 |
| P2504 [HAOI2006] 聪明的猴子 | 18 | 6 | 5 |
| P2330 [SCOI2005] 繁忙的都市 | 8 | 6 | 5 |
| P1991 无线通讯网 | 11 | 4 | 5 |
| P2872 [USACO07DEC] Building Roads S | 6 | 4 | 5 |
| P2121 拆地毯 | 18 | 5 | 5 |
章节 7. 最近公共祖先
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P3379 【模板】最近公共祖先（LCA） | 93 | 28 | 5 |
| 782 「一本通 4.4 例 1」点的距离 | 107 | 38 | 5 |
| 786 「一本通 4.4 练习 1」Dis | 78 | 38 | 4 |
| 787 「一本通 4.4 练习 2」祖孙询问 | 76 | 34 | 4 |
| 788 「一本通 4.4 练习 3」聚会 | 63 | 34 | 3 |
章节 8. 图论综合应用题单
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P1330 封锁阳光大学 | 71 | 25 | 5 |
| P2661 [NOIP 2015 提高组] 信息传递 | 13 | 8 | 5 |
| P2921 [USACO08DEC] Trick or Treat on the Farm G | 7 | 6 | 6 |
| P7831 [CCO 2021] Travelling Merchant | 20 | 9 | 8 |
| P7113 [NOIP2020] 排水系统 | 0 | 0 | 5 |
| P2498 [SDOI2012] 拯救小云公主 | 2 | 2 | 6 |
| P1967 [NOIP 2013 提高组] 货车运输 | 48 | 16 | 7 |
| P11907 [NHSPC 2023] F. 恐怖的黑色魔物 | 52 | 5 | 7 |
| P4768 [NOI2018] 归程 | 33 | 5 | 8 |
章节 9. 树上差分
以及抽象的LCA题目
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| JLOI2014E 松鼠的新家 | 114 | 44 | 5 |
| P3128 [USACO15DEC] Max Flow P | 34 | 21 | 6 |
| ACM0061 M. 王国(kingdom) | 48 | 18 | 5 |
| 785 「一本通 4.4 例 4」次小生成树 | 36 | 7 | 8 |
| TRN215 树上差分与树形DP - 扩展题单 | 51 | 43 | 1 |
章节 10. 树上DP
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P1352 没有上司的舞会 | 35 | 21 | 5 |
| P1122 最大子树和 | 42 | 14 | 5 |
| P2015 二叉苹果树 | 24 | 18 | 6 |
| P1270 “访问”美术馆 | 35 | 15 | 7 |
| P2014 [CTSC1997] 选课 | 18 | 12 | 6 |
| P2016 [SEERC 2000] 战略游戏 | 7 | 6 | 5 |
| P1273 [CHCI 2002 Final Exam #2] 有线电视网 | 20 | 12 | 6 |
| P1131 [ZJOI2007] 时态同步 | 19 | 9 | 6 |
| P4438 [HNOI/AHOI2018] 道路 | 16 | 7 | 6 |
| P2585 [ZJOI2006] 三色二叉树 | 10 | 5 | 6 |
| P1040 [NOIP 2003 提高组] 加分二叉树 | 13 | 11 | 6 |
| P2986 [USACO10MAR] Great Cow Gathering G | 25 | 10 | 6 |
| P5658 [CSP-S 2019] 括号树 | 30 | 10 | 6 |
| P3177 [HAOI2015] 树上染色 | 34 | 12 | 7 |
| P3047 [USACO12FEB] Nearby Cows G | 41 | 15 | 6 |
| P4516 [JSOI2018] 潜入行动 | 1 | 0 | 8 |
| P6847 [CEOI 2019] Magic Tree | 0 | 0 | 8 |
| P6773 [NOI2020] 命运 | 0 | 0 | 9 |
| BZOJ4919 [Lydsy1706月赛]大根堆 | 38 | 12 | 6 |
| P4577 [FJOI2018] 领导集团问题 | 25 | 13 | 8 |
章节 11. 树链剖分
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P3379 【模板】最近公共祖先（LCA） | 93 | 28 | 5 |
| 790 「一本通 4.5 例 1」树的统计 | 114 | 29 | 7 |
| JLOI2014E 松鼠的新家 | 114 | 44 | 5 |
| 793 「一本通 4.5 练习 3」染色 | 63 | 17 | 7 |
| NOI2015B 软件包管理器 (Package Manager) | 37 | 18 | 4 |
| P3178 [HAOI2015] 树上操作 | 19 | 9 | 7 |
| P3313 [SDOI2014] 旅行 | 7 | 5 | 7 |
| P3384 【模板】重链剖分 / 树链剖分 | 30 | 11 | 7 |
章节 12. 欧拉路径
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P7771 【模板】欧拉路径 | 53 | 15 | 6 |
| P1127 词链 | 0 | 0 | 6 |
| P1341 无序字母对 | 4 | 0 | 6 |
| P2731 [USACO3.3] 骑马修栅栏 Riding the Fences | 2 | 1 | 6 |
| P3443 [POI 2006] LIS-The Postman | 0 | 0 | 8 |
| P5921 [POI 1999 R3] 原始生物 | 21 | 13 | 7 |
| P6628 [省选联考 2020 B 卷] 丁香之路 | 1 | 1 | 8 |
章节 13. 连通性相关
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P3388 【模板】割点（割顶） | 67 | 12 | 6 |
| P8435 【模板】点双连通分量 | 16 | 9 | 6 |
| P8436 【模板】边双连通分量 | 15 | 8 | 6 |
| P3387 【模板】缩点 | 25 | 11 | 6 |
| D1060 加边求桥 | 55 | 12 | 7 |
| P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G | 71 | 5 | 6 |
| P4306 [JSOI2010] 连通数 | 17 | 7 | 5 |
| P5025 [SNOI2017] 炸弹 | 23 | 1 | 8 |
| TRN225 扩展题单 - 连通性相关 | 26 | 23 | 2 |
章节 14. 网络流
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| B3606 [图论与代数结构 501] 网络流_1 | 12 | 11 | 7 |
| B3607 [图论与代数结构 502] 网络流_2 | 17 | 11 | 7 |
| B3608 [图论与代数结构 601] 最小费用最大流 | 23 | 5 | 7 |
| P3376 【模板】网络最大流 | 103 | 17 | 7 |
| P3381 【模板】最小费用最大流 | 52 | 11 | 7 |
章节 15. 网络流与线性规划 24 题
1~3最短路、4~13最大流、14~23最小费用最大流、24疑似错题
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| P2761 软件补丁问题 | 1 | 1 | 6 |
| P4011 孤岛营救问题 | 1 | 1 | 7 |
| P4009 汽车加油行驶问题 | 0 | 0 | 7 |
| P2756 飞行员配对方案问题 | 10 | 5 | 6 |
| P3254 圆桌问题 | 4 | 2 | 7 |
| P2763 试题库问题 | 1 | 1 | 7 |
| P3355 骑士共存问题 | 2 | 1 | 7 |
| P2774 方格取数问题 | 14 | 6 | 8 |
| P2762 太空飞行计划问题 | 14 | 6 | 8 |
| P2766 最长不下降子序列问题 | 43 | 11 | 8 |
| P2764 最小路径覆盖问题 | 1 | 1 | 8 |
| P2765 魔术球问题 | 1 | 1 | 7 |
| P2754 [CTSC1999] 家园 / 星际转移问题 | 0 | 0 | 8 |
| P4014 分配问题 | 1 | 1 | 7 |
| P4015 运输问题 | 1 | 1 | 7 |
| P4016 负载平衡问题 | 1 | 1 | 6 |
| P4012 深海机器人问题 | 0 | 0 | 8 |
| P3356 火星探险问题 | 0 | 0 | 8 |
| P4013 数字梯形问题 | 5 | 3 | 8 |
| P2770 航空路线问题 | 0 | 0 | 8 |
| P3358 最长 k 可重区间集问题 | 0 | 0 | 8 |
| P3357 最长k可重线段集问题 | 0 | 0 | 8 |
| P1251 餐巾计划问题 | 0 | 0 | 8 |
| P2775 机器人路径规划问题（疑似错题） | 0 | 0 | (无) |
- 参加人数
- 80
- 创建人
-
33DAI