# CSP-S 图论算法模板速查 7/10 洛谷月赛复习用所有模板均使用链式前向星建图。 --- ## 0. 通用头文件 注意事项 cpp #include cstdio // scanf/printf #include cstring // memset #include queue // queue, priority_queue #include vector // vectorpriority_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((VE)logV) **不能处理负权边** cpp #include cstdio #include cstring #include queue #include vector using namespace std; typedef pairint, int pii; // pii pairint,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)); // 所有距离初始化为INF0x3f按字节填充 memset(vis, 0, sizeof(vis)); // vis全部清零 dist[s] 0; // 源点到自己的距离为0 // 小顶堆堆顶是距离最小的节点 // 写法priority_queue类型, 底层容器, 比较器greater表示小顶堆 priority_queuepii, vectorpii, greaterpii 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必须为-10不是空 | | 漏 if(vis[u])continue | 必须加懒删除否则TLE | | 漏 typedef pairint,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表示未访问 queueint 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] 1u是当前节点 | | 下标拼写错误 | 仔细检查 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_queueint pq; // 小顶堆写法 priority_queueint, vectorint, greaterint pq; // 存pair第一维是距离第二维是节点号 priority_queuepii, vectorpii, greaterpii 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 不是 0x3f3f3f3fmemset 按字节填充 4. **数据范围**看清题目n 和 m 的范围决定数组大小 5. **输入格式**有向图 vs 无向图权值有无 6. **输出格式**空格、换行、左对齐右对齐 ### Dev-C 本地调试注意 - **不要写** ios::sync_with_stdio(0) — 本地会导致输入异常 - 洛谷提交时可以加这行加速 - 用 scanf/printf 更安全不容易出问题 ### 时间分配建议月赛 - 前 10 分钟通读所有题标记难度 - 先做有把握的题T1 通常最简单 - 不会的题先写暴力部分分 0 分 - 最后 15 分钟检查已有代码的边界情况