树：A1335-A1340，A1363-A1368
图：A1341-A1350
Login to join training plan
前置知识（在“基本数据结构”训练中可以找到习题）：
- 二叉树、多叉树的表示和存储
- 图的表示和存储（邻接表、邻接矩阵、链式前向星）
- 树和图的 DFS、BFS
- 洪水填充（Flood Fill）
- 求图的连通分量数
本训练包括以下内容（图论的基本算法）：
- 最短路径算法（BF、SPFA、Dijkstra、Floyd）
- 最小生成树算法（Prim、Kruskal）
- 拓扑排序
1.Dijkstra 算法、优先队列.pdf 1.Dijkstra 算法、优先队列.pdf
2.Bellman–Ford、SPFA算法.pdf 2.Bellman–Ford、SPFA算法.pdf
Section 1. 优先队列
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| A1369 合并果子(fruit) | 85 | 35 | 5 |
| A1371 看病 | 44 | 20 | 4 |
| A1372 小明的账单 | 31 | 19 | 3 |
| A1373 鱼塘钓鱼(fishing） | 20 | 9 | 7 |
Section 2. 最短路径
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3371 【模板】单源最短路径（弱化版） | 225 | 35 | 8 |
| P4779 【模板】单源最短路径（标准版） | 181 | 24 | 8 |
| A1344 【例4-4】最小花费 | 65 | 14 | 7 |
| P1144 最短路计数 | 53 | 13 | 7 |
| P1629 邮递员送信 | 30 | 12 | 6 |
| A1377 最优乘车(travel) | 62 | 9 | 8 |
| P3385 【模板】负环 | 101 | 14 | 8 |
| P1807 最长路 | 52 | 8 | 8 |
| P2850 [USACO06DEC] Wormholes G | 22 | 2 | 9 |
| P1088 拉近距离 | 63 | 4 | 9 |
| A1342 【例4-1】最短路径问题【Floyd模板】 | 82 | 29 | 5 |
| A1343 【例4-2】牛的旅行 | 7 | 4 | 10 |
| P2910 [USACO08OPEN] Clear And Present Danger S | 4 | 3 | 10 |
| P6464 [传智杯 #2 决赛] 传送门 | 7 | 3 | 10 |
Section 3. 并查集
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| A1346 【例4-7】亲戚(relation) | 87 | 29 | 6 |
| A1347 【例4-8】格子游戏 | 15 | 7 | 8 |
| A1385 团伙(group) | 21 | 9 | 7 |
| A1386 打击犯罪(black) | 9 | 4 | 9 |
| A1387 搭配购买(buy) | 30 | 6 | 8 |
| A1388 家谱(gen) | 15 | 5 | 8 |
| A1389 亲戚 | 22 | 9 | 7 |
| P2661 [NOIP2015 提高组] 信息传递 | 6 | 3 | 10 |
| P1955 [NOI2015] 程序自动分析 | 1 | 1 | 10 |
Section 4. 最小生成树
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3366 【模板】最小生成树 | 143 | 28 | 7 |
| A1391 局域网(net) | 57 | 24 | 5 |
| P1194 买礼物 | 63 | 8 | 8 |
| P1195 口袋的天空 | 3 | 3 | 10 |
| P1550 [USACO08OCT] Watering Hole G | 7 | 5 | 9 |
| P2700 逐个击破 | 2 | 2 | 10 |
Section 5. 拓扑排序、欧拉路
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| A1351 【例4-12】家谱树 | 56 | 27 | 4 |
| P4017 最大食物链计数 | 69 | 19 | 6 |
| P1113 杂务 | 39 | 11 | 7 |
| A1396 病毒(virus) | 6 | 1 | 10 |
| A1395 烦人的幻灯片(slides) | 4 | 1 | 10 |
| A1352 【例4-13】奖金 | 9 | 1 | 10 |
| P1347 排序 | 1 | 1 | 10 |
| A1375 骑马修栅栏(fence) | 85 | 12 | 8 |
| P7771 【模板】欧拉路径 | 69 | 7 | 9 |
