# CSP-S 图论算法模板速查 > 7/10 洛谷月赛复习用，所有模板均使用链式前向星建图。 --- ## 0. 通用头文件 & 注意事项 ```cpp #include <cstdio> // scanf/printf #include <cstring> // memset #include <queue> // queue, priority_queue #include <vector> // vector（priority_queue小顶堆需要） #include <algorithm> // sort using namespace std; // 注意：Dev-C++ 本地调试时不要写 ios::sync_with_stdio(0)，会导致输入异常 // 洛谷提交时可以加，加速I/O ``` --- ## 1. 链式前向星建图（所有图论算法的基础） ```cpp const int MAXN = 100005; // 最大节点数 const int MAXM = 500005; // 最大边数（无向图要开2倍） int head[MAXN]; // head[u] = 节点u的第一条边的编号（-1表示无边） int to[MAXM]; // to[i] = 第i条边的终点 int we[MAXM]; // we[i] = 第i条边的权值 int nxt[MAXM]; // nxt[i] = 第i条边的下一条边（同起点的链表） int cnt; // 边的计数器（从0开始） // 初始化：memset(head, -1, sizeof(head)); cnt = 0; // 加边函数（头插法） void add(int u, int v, int w) { to[cnt] = v; // 记录终点 we[cnt] = w; // 记录权值 nxt[cnt] = head[u]; // 新边指向原来的第一条边 head[u] = cnt; // head[u] 更新为新边 cnt++; // 边计数器+1 } // 遍历节点u的所有邻接边： // for (int i = head[u]; ~i; i = nxt[i]) { // ~i 等价于 i != -1 // int v = to[i], w = we[i]; // // 处理... // } // 无向图：add(u, v, w); add(v, u, w); // 正反各加一次 // 有向图：add(u, v, w); // 只加一次 ``` --- ## 2. Dijkstra（堆优化，单源最短路径） > **适用场景**：非负权图，求单源最短路径 > **复杂度**：O((V+E)logV) > **不能处理负权边！** ```cpp #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; typedef pair<int, int> pii; // pii = pair<int,int>，第一维存距离，第二维存节点 const int MAXN = 100005; const int MAXM = 500005; const int INF = 0x3f3f3f3f; // 无穷大（约10亿），用0x3f初始化memset int head[MAXN], to[MAXM], we[MAXM], nxt[MAXM], cnt; int dist[MAXN]; // dist[i] = 源点到i的最短距离 bool vis[MAXN]; // vis[i] = 节点i是否已确定最短路（懒删除标记） void add(int u, int v, int w) { to[cnt] = v; we[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt++; } void dijkstra(int s, int n) { // 第1步：初始化 memset(dist, 0x3f, sizeof(dist)); // 所有距离初始化为INF（0x3f按字节填充） memset(vis, 0, sizeof(vis)); // vis全部清零 dist[s] = 0; // 源点到自己的距离为0 // 小顶堆：堆顶是距离最小的节点 // 写法：priority_queue<类型, 底层容器, 比较器>，greater表示小顶堆 priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, s}); // {距离, 节点}，源点入堆 while (!pq.empty()) { // 第2步：取堆顶（当前距离最小的节点） pii p = pq.top(); pq.pop(); int d = p.first, u = p.second; // 第3步：懒删除——如果u已经确定最短路，跳过 // （同一个节点可能多次入堆，只处理第一次） if (vis[u]) continue; vis[u] = true; // 第4步：遍历u的所有邻接边，进行松弛操作 for (int i = head[u]; ~i; i = nxt[i]) { int v = to[i], w = we[i]; // 松弛：如果经过u到v更近，就更新dist[v] if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); // 更新后入堆 } } } // 循环结束后，dist[i]就是源点到i的最短距离 } int main() { int n, m, s; scanf("%d%d%d", &n, &m, &s); memset(head, -1, sizeof(head)); // 【易错】head必须初始化为-1 cnt = 0; for (int i = 0; i < m; ++i) { // 【易错】循环m次读m条边，不是n次 int u, v, w; scanf("%d%d%d", &u, &v, &w); add(u, v, w); // 有向图只加一次 } dijkstra(s, n); for (int i = 1; i <= n; ++i) printf("%d ", dist[i]); printf("\n"); return 0; } ``` ### Dijkstra 常见错误清单 | 错误 | 正确写法 | |------|---------| | `memset(dist, 0x3f3f3f3f, ...)` | `memset(dist, 0x3f, ...)`（memset按字节填充） | | `memset(head, 0, ...)` | `memset(head, -1, ...)`（head必须为-1，0不是"空"） | | 漏 `if(vis[u])continue` | 必须加懒删除，否则TLE | | 漏 `typedef pair<int,int> pii` | 不写pii会编译报错 | | 声明 `we[]` 但用 `w[]` | 数组名必须一致 | | 循环 `i < n` 读边 | 应该 `i < m`（读m条边不是n条） | --- ## 3. 并查集（Kruskal的基础组件） ```cpp int fa[MAXN]; // fa[i] = 节点i的父节点 // 初始化：每个节点的父节点是自己 void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; } // 查找根节点（带路径压缩） // 路径压缩：查找过程中顺便把所有节点直接指向根，下次O(1) int find(int x) { if (fa[x] == x) return x; // 找到根节点 return fa[x] = find(fa[x]); // 递归找根，同时路径压缩 } // 合并两个集合（把x的根挂到y的根下面） void unite(int x, int y) { int rx = find(x), ry = find(y); if (rx != ry) fa[rx] = ry; // 不同集合才合并 } // 判断两个节点是否在同一集合 bool same(int x, int y) { return find(x) == find(y); } ``` --- ## 4. Kruskal（最小生成树） > **适用场景**：求连通图的最小生成树 > **复杂度**：O(ElogE)（排序是瓶颈） > **核心思想**：贪心——按边权从小到大排序，用并查集判环 ```cpp #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 5005; const int MAXM = 200005; struct Edge { int u, v, w; // 起点、终点、权值 }; Edge e[MAXM]; // 存所有边 int fa[MAXN]; // 并查集父节点 // 边的比较函数：按权值从小到大排序 bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; } // 并查集查找（带路径压缩） int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } int main() { int n, m; scanf("%d%d", &n, &m); // 第1步：读入所有边 for (int i = 0; i < m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); // 第2步：按边权排序（贪心：从小到大选边） sort(e, e + m, cmp); // 第3步：初始化并查集 for (int i = 1; i <= n; ++i) fa[i] = i; // 第4步：遍历排序后的边，选n-1条 int ans = 0; // 最小生成树总权值 int cnt_edge = 0; // 已选边的数量 for (int i = 0; i < m; ++i) { int fu = find(e[i].u), fv = find(e[i].v); if (fu != fv) { // 不在同一集合 → 不会成环 → 可以选 fa[fu] = fv; // 合并 ans += e[i].w; // 累加权值 cnt_edge++; // 计数+1 if (cnt_edge == n - 1) break; // 【易错】选够n-1条就停止 } } // 第5步：检查图是否连通 if (cnt_edge < n - 1) printf("orz\n"); // 图不连通，无法生成MST else printf("%d\n", ans); return 0; } ``` ### Kruskal 常见错误清单 | 错误 | 正确写法 | |------|---------| | 忘记 `fa[i] = i` 初始化 | 必须在选边前初始化并查集 | | 忘记 `break` | 选够 n-1 条边后必须停止 | | find 不加路径压缩 | `fa[x] = find(fa[x])` 必须写 | | 无向图边只读一次 | 无向图要读两次（u→v 和 v→u）| --- ## 5. BFS（广度优先搜索，链式前向星版） > **适用场景**：无权图最短路径、层序遍历、迷宫最短路 > **核心**：队列 + vis标记，入队时标记 ```cpp #include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN = 1005; int head[MAXN], to[MAXM], nxt[MAXM], cnt; int dist[MAXN]; // dist[i] = 起点到i的步数（兼做vis：-1表示未访问） queue<int> q; void add(int u, int v) { to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt++; } void bfs(int s) { memset(dist, -1, sizeof(dist)); // -1表示未访问 dist[s] = 0; // 起点步数为0 q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; ~i; i = nxt[i]) { int v = to[i]; if (dist[v] == -1) { // 【易错】入队时检查未访问 dist[v] = dist[u] + 1; // 步数 = 上一步 + 1 q.push(v); // 入队时标记，不是出队时 } } } } ``` ### BFS 常见错误清单 | 错误 | 正确写法 | |------|---------| | 用递归代替队列 | BFS必须用queue，不能用递归（那是DFS） | | 出队时才标记vis | 入队时就标记，防止重复入队 | | 步数用错变量 | `dist[v] = dist[u] + 1`，u是当前节点 | | 下标拼写错误 | 仔细检查 `vis[nx][ny]` 不要写成 `vis[nx][nx]` | --- ## 6. DFS（深度优先搜索，链式前向星版） > **适用场景**：全排列、连通块、路径搜索 > **核心**：递归 + 回溯 ```cpp #include <cstdio> #include <cstring> using namespace std; const int MAXN = 15; int n; int path[MAXN]; // 当前排列 bool vis[MAXN]; // vis[i] = 数字i是否已使用 // DFS全排列模板 void dfs(int k) { if (k == n) { // 递归终点：填满了n个位置 for (int i = 0; i < n; ++i) printf("%d ", path[i]); printf("\n"); return; } for (int i = 1; i <= n; ++i) { if (!vis[i]) { // 数字i未使用 path[k] = i; // 选i放入当前位置 vis[i] = true; // 标记已使用 dfs(k + 1); // 递归填下一个位置 vis[i] = false; // 【关键】回溯：撤销选择 } } } int main() { scanf("%d", &n); memset(vis, 0, sizeof(vis)); dfs(0); return 0; } ``` --- ## 7. priority_queue 小顶堆速记 ```cpp // 大顶堆（默认）：priority_queue<int> pq; // 小顶堆写法： priority_queue<int, vector<int>, greater<int>> pq; // 存pair：第一维是距离，第二维是节点号 priority_queue<pii, vector<pii>, greater<pii>> pq; // greater按pair的第一维比较 → 距离最小的在堆顶 // 操作： // pq.push({dist, node}); // 入堆 // pq.top(); // 看堆顶（不删除） // pq.pop(); // 删堆顶 // pq.empty(); // 是否为空 ``` --- ## 8. 月赛注意事项 ### 提交前检查清单 1. **head 初始化**：`memset(head, -1, sizeof(head))` — 忘了全炸 2. **数组大小**：无向图边数开 2 倍 3. **memset 填充值**：`0x3f` 不是 `0x3f3f3f3f`（memset 按字节填充） 4. **数据范围**：看清题目，n 和 m 的范围决定数组大小 5. **输入格式**：有向图 vs 无向图，权值有无 6. **输出格式**：空格、换行、左对齐右对齐 ### Dev-C++ 本地调试注意 - **不要写** `ios::sync_with_stdio(0)` — 本地会导致输入异常 - 洛谷提交时可以加这行加速 - 用 `scanf/printf` 更安全，不容易出问题 ### 时间分配建议（月赛） - 前 10 分钟：通读所有题，标记难度 - 先做有把握的题（T1 通常最简单） - 不会的题先写暴力（部分分 > 0 分） - 最后 15 分钟：检查已有代码的边界情况
