树：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) | 104 | 42 | 5 |
| A1371 看病 | 47 | 21 | 4 |
| A1372 小明的账单 | 34 | 20 | 3 |
| A1373 鱼塘钓鱼(fishing） | 22 | 10 | 6 |
Section 2. 最短路径
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3371 【模板】单源最短路径（弱化版） | 336 | 43 | 8 |
| P4779 【模板】单源最短路径（标准版） | 228 | 31 | 8 |
| A1344 【例4-4】最小花费 | 75 | 17 | 7 |
| P1144 最短路计数 | 65 | 17 | 7 |
| P1629 邮递员送信 | 42 | 16 | 5 |
| A1377 最优乘车(travel) | 74 | 11 | 8 |
| P3385 【模板】负环 | 184 | 20 | 9 |
| P1807 最长路 | 71 | 11 | 8 |
| P2850 [USACO06DEC] Wormholes G | 32 | 4 | 9 |
| P1088 拉近距离 | 80 | 5 | 9 |
| A1342 【例4-1】最短路径问题【Floyd模板】 | 106 | 33 | 6 |
| A1343 【例4-2】牛的旅行 | 8 | 4 | 10 |
| P2910 [USACO08OPEN] Clear And Present Danger S | 7 | 5 | 9 |
| P6464 [传智杯 #2 决赛] 传送门 | 9 | 4 | 9 |
Section 3. 并查集
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| A1346 【例4-7】亲戚(relation) | 149 | 38 | 7 |
| A1347 【例4-8】格子游戏 | 33 | 18 | 4 |
| A1385 团伙(group) | 42 | 15 | 6 |
| A1386 打击犯罪(black) | 22 | 5 | 8 |
| A1387 搭配购买(buy) | 36 | 9 | 7 |
| A1388 家谱(gen) | 15 | 5 | 8 |
| A1389 亲戚 | 29 | 11 | 6 |
| P2661 [NOIP2015 提高组] 信息传递 | 18 | 4 | 9 |
| P1955 [NOI2015] 程序自动分析 | 35 | 3 | 9 |
Section 4. 最小生成树
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P3366 【模板】最小生成树 | 162 | 36 | 7 |
| A1391 局域网(net) | 70 | 28 | 5 |
| P1194 买礼物 | 64 | 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】家谱树 | 86 | 32 | 5 |
| P4017 最大食物链计数 | 75 | 19 | 7 |
| P1113 杂务 | 41 | 12 | 6 |
| A1396 病毒(virus) | 6 | 1 | 10 |
| A1395 烦人的幻灯片(slides) | 4 | 1 | 10 |
| A1352 【例4-13】奖金 | 9 | 1 | 10 |
| P1347 排序 | 1 | 1 | 10 |
| A1375 骑马修栅栏(fence) | 87 | 13 | 8 |
| P7771 【模板】欧拉路径 | 71 | 8 | 9 |
