企业官网建设流程全解析

打算法竞赛的同学应该都有体会，图论相关的模板总是占代码量的大头。平时刷题倒还好，一到正式比赛，短暂的时间内既要读题、想解法、调试，还得从零手撸一遍最短路、最小生成树，那种紧张感我到现在都记得。后来我把自己常用的图论模板整理成了固定的一套，每次直接抄，比赛时省下来的时间全用来分析和验证思路，效果特别好。这篇文章就把我平时高频使用的图论算法模板做个汇总，附上一些容易踩坑的细节，适合正在学图论、备战ACM或NOIP的读者参考。

我整理的这些模板都用C++写，遵循几个原则：能用数组就不用复杂容器、能静态就坚决不动态分配、所有代码都压到尽量短且不容易写错的结构。这么做不是炫技，而是比赛环境下，代码越短、越贴近自己熟悉的格式，越不容易在紧张时写出隐蔽bug。下面我按照最短路、最小生成树、拓扑排序、二分图这几个常见模块来拆解。

1. 模板的整体设计思路与准备工作

1.1 为什么比赛选手需要固定模板

先说一个很多人忽略的事实：图论题真正难的不是背模板，而是把问题抽象成图。但抽象完了，如果基础代码都写不顺，思路再漂亮也白搭。比如最短路里的Dijkstra，堆优化写法如果不熟练，现场调试队列优先级、dist数组更新顺序，随随便便就花掉二十分钟。而一套固定的、自己亲手验证过的模板，可以把写代码的时间压缩到两三分钟，把精力留给真正的思考。

我自己早期也犯过这个毛病：每次写模板都重开一份，觉得反正会写，直接上手就行。后来发现写出来的代码风格不一致，一会儿用vector邻接表，一会儿用链式前向星，出错了自己都看不清。整理模板之后，不仅写题快了，出错率也明显下降，因为每个模板都反复使用过，边界条件和陷阱都烂熟于心。

1.2 模板的通用存储方式：链式前向星还是vector邻接表

这是我在实战中最纠结过的选择。vector存邻接表写起来很直观，遍历也方便，但比赛偶尔会遇到卡时间的题，vector的push_back会有一定开销，而且封装成结构体后内存不连续，对缓存不友好。链式前向星写起来稍微绕一点，用数组模拟链表，但效率高、空间紧凑，而且支持多重边，所以在竞赛环境里我更推荐链式前向星。

struct Edge { int to, w, nxt; } e[MAXM]; int head[MAXN], tot; void init() { memset(head, -1, sizeof(head)); tot = 0; } void addEdge(int u, int v, int w) { e[tot].to = v; e[tot].w = w; e[tot].nxt = head[u]; head[u] = tot++; }

这里head数组初始化为-1，遍历时用for(int i = head[u]; i != -1; i = e[i].nxt)，非常好用。需要注意的是addEdge是无向图的时候要调用两次，把u-v和v-u都加进去。有重边的情况下这种写法天然支持，因为新增的边会插到链表头部，不会覆盖已有边。

1.3 模板的注释与变量命名习惯

我整理模板的原则是：变量名尽量短但可读，比如u、v表示端点，w表示边权，dist、vis这种一眼就能看懂。注释这块，我的建议是模板里只写关键提示，比如“这里为什么要判vis”，而不是把每一行都注释一遍。注释写多了，比赛时反而干扰阅读。

还有一点很重要，所有数组大小都预留了MAXN和MAXM的宏定义，每次使用前按题目要求改这两个值就行。我习惯把上限设为题目上限加10，防止边界访问越界。这个习惯帮我避免了不少RE（Runtime Error），你想一下如果n刚好等于数组长度，访问n+1的位置就炸了，所以多开几个位置是性价比极高的防御。

2. 最短路算法模板：Dijkstra、SPFA与Floyd

2.1 堆优化的Dijkstra（单源非负权最短路）

Dijkstra是图论里出镜率最高的算法，核心思想是贪心：每次从未确定的点中选出距离最小的点，用它去松弛连边。当边权非负时，这个贪心是正确的。朴素写法每次找最小距离需要O(n)，堆优化后用优先队列把这一步降到O(logn)，整体复杂度O((n+m)logn)，适用于大多数字典序或者路径统计类题目。

typedef pair<int, int> PII; // {distance, vertex} const int INF = 0x3f3f3f3f; void dijkstra(int s) { priority_queue<PII, vector<PII>, greater<PII> > pq; for (int i = 1; i <= n; i++) dist[i] = INF; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { PII p = pq.top(); pq.pop(); int d = p.first, u = p.second; if (d != dist[u]) continue; // 过期标记 for (int i = head[u]; i != -1; i = e[i].nxt) { int v = e[i].to, w = e[i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }

这里有个细节，pair排序时先按距离再按点编号，所以在优先队列里用greater<PII>就能得到小顶堆。还有一个很多新手不理解的地方，为什么不用vis数组标记已确定的点。因为优先队列里可能出现同一个点被多次push的情况，第一次出队的才是最小距离，后面出队的距离一定更大，用if(d != dist[u]) continue;直接跳过即可，效果等价于vis但代码更简洁。

注意：这里INF用0x3f3f3f3f而不是INT_MAX，是因为后面如果做dist[u] + w，INT_MAX+正数会溢出变成负数，直接导致算法出错。0x3f3f3f3f足够大，两个相加也不会溢出int范围。

2.2 SPFA与负权图的处理

SPFA本质是Bellman-Ford的队列优化，适合判断负环或者边权存在负数的情况。它的思想是：只有被松弛过的点才可能引起其他点的松弛，所以用一个队列维护被更新过的点，反复入队出队。虽然SPFA在随机图上的表现不错，但出题人会构造网格图或者菊花图卡它，最坏复杂度还是O(nm)，所以遇到不存在负权的题，老老实实用Dijkstra。

bool inq[MAXN]; int cnt[MAXN]; // 记录入队次数，用于判断负环 bool spfa(int s) { queue<int> q; memset(dist, 0x3f, sizeof(dist)); memset(inq, false, sizeof(inq)); memset(cnt, 0, sizeof(cnt)); dist[s] = 0; q.push(s); inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = head[u]; i != -1; i = e[i].nxt) { int v = e[i].to, w = e[i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!inq[v]) { q.push(v); inq[v] = true; if (++cnt[v] > n) return false; // 存在负环 } } } } return true; }

判断负环的原理是，从任意点出发到某个点的最短路最多经过n-1条边，如果一个点的入队次数大于n，说明存在一条被反复松弛的负权回路。这个模板我在做差分约束系统题目的时候也经常用，因为它能检测出不满足约束条件的环。注意，如果题目明确没有负环，也可以去掉cnt数组这部分，只保留松弛逻辑，代码会更短。

2.3 Floyd多源最短路与动态规划视角

Floyd的代码极短，三层循环就完了，但它背后的动态规划思想容易被忽略。dp[k][i][j]表示从i到j、中间只经过编号小于等于k的点时，最短路的长度。最终答案就是dp[n][i][j]。滚动掉第一维后就变成了标准的二维Floyd写法。

for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (mp[i][j] > mp[i][k] + mp[k][j]) mp[i][j] = mp[i][k] + mp[k][j];

这里的初始化要注意：mp[i][i]=0，其他点对如果有边就设为边权，没有边就设为INF。为什么k要在最外层？因为mp[i][j]在更新时用到的mp[i][k]和mp[k][j]必须是只经过前k-1个中间点的结果，如果k放在内层，会提前使用包含k这条路径的信息，导致重复经过k点，结果就不对了。Floyd适合n不超过500的场景，复杂度O(n^3)，超过这个规模就得考虑Johnson算法或者跑n次Dijkstra了。

3. 并查集与最小生成树模板

3.1 带路径压缩和按秩合并的并查集

并查集其实不算严格的图论算法，但它在判断连通性、找环、合并集合上太常用了，几乎每道图论题都能用上。路径压缩把树的高度压到接近O(1)，按秩合并能保证树的高度始终保持在对数级别，两者结合后单次操作的均摊复杂度接近常数。

int fa[MAXN], rnk[MAXN]; void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; memset(rnk, 0, sizeof(rnk)); } int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rnk[x] < rnk[y]) swap(x, y); fa[y] = x; if (rnk[x] == rnk[y]) rnk[x]++; }

这里有个小坑：find递归在链很长时虽然路径压缩后会变短，但极端情况下第一次递归可能深度很大，导致栈溢出。通常题目给的数据范围不会那么极限，但如果你用这套模板跑百万级别的数据，建议改成非递归版本，或者把rnk换成fa数组的负值表示集合大小。非递归find有一种写法很简单，先用循环找到根，再把路径上所有点平铺到根上，性能非常稳定。

经验：我在处理“判断一棵树是否形成环”这种问题时，会边读边做unite。每次连边时若两个端点已经在同一集合里，说明这条边会形成环，记录下来即可。这个技巧在Kruskal算法里也是核心判断逻辑。

3.2 Kruskal最小生成树与贪心证明

Kruskal的思路特别简单：把所有边按权值从小到大排序，依次尝试加入生成树，如果这条边的两个端点不在同一个连通块里就加入，否则跳过。这个贪心正确性可以用反证法证明，我们在这里不展开，但实践中记住结论就够用。

struct Line { int u, v, w; } edge[MAXM]; bool cmp(Line a, Line b) { return a.w < b.w; } int kruskal(int n, int m) { int ans = 0, cnt = 0; sort(edge, edge + m, cmp); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 0; i < m; i++) { int u = edge[i].u, v = edge[i].v, w = edge[i].w; u = find(u); v = find(v); if (u != v) { fa[u] = v; ans += w; cnt++; if (cnt == n - 1) break; } } return cnt == n - 1 ? ans : -1; // -1表示图不连通 }

这个模板里最值钱的变量是cnt，它统计已经加入的边数。最小生成树在n个点的图上一定恰好有n-1条边，如果跑完所有边还没凑够，说明图本身不连通。用这个返回值判断一下，很多题目会问“能否构成生成树”，这样一次Kruskal就同时求了最小权和连通性。

3.3 Prim算法与稠密图的场景适配

Prim的思路和Dijkstra极像，也是贪心地向外扩展，区别在于Prim维护的是“当前点到已选集合的最短距离”，而不是到起点的最短距离。朴素Prim适合稠密图，复杂度O(n^2)，堆优化版O((n+m)logn)反而在稠密图上不如朴素版，因为堆操作常数太大。如果题目给的m接近n^2，就直接写朴素Prim。

int prim(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] = 0; int ans = 0; for (int i = 1; i <= n; i++) { int u = -1, minDist = INF; for (int j = 1; j <= n; j++) { if (!vis[j] && (u == -1 || dist[j] < minDist)) { u = j; minDist = dist[j]; } } if (u == -1) return -1; vis[u] = true; ans += dist[u]; for (int j = 1; j <= n; j++) { if (!vis[j] && mp[u][j] < dist[j]) { dist[j] = mp[u][j]; } } } return ans; }

Prim里的mp[u][j]是邻接矩阵，所以它天然适合稠密图。注意这里ans += dist[u]，而不是minDist累加，实际上两者是一样的，但我习惯用dist[u]，因为遍历之后dist[u]已经被更新成最小值了。还有一个细节点，我用的vis是bool数组标记点是否已经在生成树集合里，这个和Dijkstra的vis含义不同，别搞混。

4. 拓扑排序与有向无环图的应用

4.1 Kahn算法的BFS实现

拓扑排序解决的是“有没有一个合法的线性顺序，使得所有有向边都从前往后指”的问题。典型应用是课程依赖、编译依赖、项目排期。Kahn算法维护一个入度为0的队列，不断取出队首顶点、删除它的出边、更新后续顶点的入度，直到队列为空。

int indeg[MAXN]; vector<int> topo; bool topoSort(int n) { queue<int> q; for (int i = 1; i <= n; i++) { if (indeg[i] == 0) q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for (int i = head[u]; i != -1; i = e[i].nxt) { int v = e[i].to; if (--indeg[v] == 0) q.push(v); } } return (int)topo.size() == n; }

最后这个topo.size() == n非常关键。如果图里有环，环上的节点入度永远不为0，拓扑序列长度就会小于n，用这个来判断图是否为DAG（有向无环图）很直接。最后如果要输出拓扑序，直接遍历topo就行。如果题目要求字典序最小的拓扑序，把queue换成priority_queue，小于号改成大于号（即小顶堆）就行，代码只改一个地方。

4.2 拓扑排序与最短最长路结合

有时候图里有多个入度为0的起点，要求某个终点完成的最早时间或最晚时间，这就是拓扑排序加DP的经典套题。处理方式是在拓扑排序的同时维护一个f[i]数组，表示到达点i的最大值或最小值，每松弛一条边就更新一次。因为拓扑序天然保证了所有前驱点都在当前点之前处理完，所以传递性很好写。

// 求最早完成时间，边权表示依赖耗时 f[v] = max(f[v], f[u] + w); // 求最长路（DAG上的动态规划） // 求最短路的场景则把max改成min，但注意不能有负边和环

这种写法比跑一遍SPFA或者Dijkstra快得多，因为没有环，只需要O(n+m)线性时间。我遇到好几个“任务调度”类型的题都用这个套路，比如POJ上的__"Genealogical tree"__和“关键路径”问题。关键路径本质就是DAG上从源点到汇点的最长路，用拓扑序DP就能解。如果你对这类题不熟，可以找几道带权DAG的题练一练，很快就上手。

5. 二分图判定与匈牙利匹配模板

5.1 染色法判定二分图

二分图是指能把所有顶点分成两个集合，每条边的两个端点分别在两个集合里。一个图是二分图，当且仅当它不包含奇环（长度为奇数的环）。染色法从任意未染色的点出发，标记为颜色1，把邻居标记为颜色2，再递归处理邻居的邻居，如果发现相邻点颜色相同，就说明存在矛盾。

bool dfs(int u, int color) { col[u] = color; for (int i = head[u]; i != -1; i = e[i].nxt) { int v = e[i].to; if (col[v] == color) return false; if (col[v] == 0 && !dfs(v, -color)) return false; } return true; } bool solve(int n) { memset(col, 0, sizeof(col)); for (int i = 1; i <= n; i++) { if (col[i] == 0 && !dfs(i, 1)) return false; } return true; }

注意这里用-color来切换颜色，代码特别干净。主函数里循环所有点是因为图可能不连通，每个连通块单独染色。这个模板在“关押罪犯”这类题里作为判定函数非常好用，配合二分答案可以解决带限制的图着色问题。

5.2 匈牙利算法求最大匹配

匈牙利算法解决的是“最多能凑出多少对互不冲突的配对”问题。核心思路是寻找增广路，如果当前这个左点v没有匹配，或者它匹配的右点能让出来位置，就更新匹配关系。这个道理听起来抽象，但代码里就一个递归函数。

int match[MAXN]; // 右点匹配的左点编号 bool used[MAXN]; // 右点是否在当前尝试占用的路径中 bool findPath(int u) { for (int i = head[u]; i != -1; i = e[i].nxt) { int v = e[i].to; if (used[v]) continue; used[v] = true; if (match[v] == 0 || findPath(match[v])) { match[v] = u; return true; } } return false; } int hungary(int n) { int res = 0; memset(match, 0, sizeof(match)); for (int i = 1; i <= n; i++) { memset(used, false, sizeof(used)); if (findPath(i)) res++; } return res; }

这里有一个关键点必须说清楚：used数组不是表示“这个右点已经被匹配过了”，而是表示“在当前这一轮的findPath尝试中，这个右点已经被占用”。如果不重置或者理解错了，就会导致递归死循环或者跳过某些可能的路径。我刚开始学匈牙利算法的时候，就在这里栽过跟头，总是把used和match搞混。

匈牙利算法复杂度O(n*m)，n是点数，m是边数。虽然理论上看起来不小，但实际表现非常快，因为很多时候提前返回了。如果要给二分图匹配问题做优化，可以有时间再了解HK算法（Hopcroft-Karp），比赛里用匈牙利一般够用。

6. 常见问题与排查技巧实录

6.1 多组测试数据时忘记初始化

这是我能想到的最常见的图论模板翻车现场。很多题目有T组测试数据，如果你只写一个全局初始化函数，但忘了在循环内调用，那么上一组数据留下的vis、dist、head数组就会污染下一组结果。我自己的经验是写一个init(n)函数把head设为-1、tot置0、并查集重置等全部做掉，并且在读入每组数据的最开始调用它。

6.2 DFS爆栈的替代方案

有些图论题需要用DFS（比如染色法、匈牙利算法），但数据规模一大，递归深度可能达到10的5次方以上，系统栈就爆了。解决办法有两个：第一个是用#pragma comment(linker, "/STACK:1024000000,1024000000")（Windows环境下），或者参考系统设定加大栈空间；第二个是改写成非递归版本。说实话，在正式比赛中选手通常无法控制编译器参数，所以写递归模板时要意识到这个风险，必要时改成栈模拟。

6.3 数组下标从0还是从1

图论的题有两种编号习惯：有的从0开始，有的从1开始。这本身不是问题，问题是模板默认从1开始，但读入数据是从0开始的，忘了转换就会导致访问到错误节点。我在模板的注释里专门写了“从1开始编号，如果是0-based请在所有读入的位置+1”。这种因为编号习惯不同而导致的bug特别难查，因为逻辑完全正确，就是差了一个偏移。

6.4 邻接矩阵的初始化与INF选择

使用Floyd或Prim时，邻接矩阵需要初始化为INF，但选INF时要注意两点：不能太大（相加会溢出），不能太小（比标准最短路还短）。我常用0x3f3f3f3f，因为它的十进制是1061109567，不到int上限的一半，两个相加大约是2.1e9，刚好还在int范围内。如果题目给的边权最大是10^9，那INF就改成0x1f1f1f1f之类的值，确保两倍INF仍然不溢出。

6.5 重边和自环的处理

链式前向星天然容忍重边，因为所有边都存下来了，Dijkstra会自行判断最小的那一条作为有效路径。但Prim用邻接矩阵时，重边需要取最小值，自环则直接忽略（因为mp[i][i]=0本身就代表不选择自环）。读入的时候可以做个判断，如果是重边就保持最小边权，否则后读入的大边会覆盖小边，导致错误。

7. 模板库的构建思路与维护建议

7.1 按照模块分类整理

我会把模板库分成这几个文件：graph_basic.cpp（链式前向星、并查集）、shortest_path.cpp（Dijkstra、SPFA、Floyd）、mst.cpp（Kruskal、Prim）、dag.cpp（拓扑排序、关键路径）、bipartite.cpp（染色法、匈牙利算法）。每个文件开头写一段注释，标出适用场景和数据范围限制。这样比赛时可以快速定位要抄哪一段。

7.2 定期用自己的模板重刷题

光收藏模板没有用，自己写熟了才叫自己的。我建议每周选两到三个图论经典题，用模板库里的代码跑一遍，顺便检查有没有可以优化的细节。比如我发现堆优化的Dijkstra在某些时候用dist > d + w这种判断比dist - w > d更安全，因为后者可能在溢出时出问题，这个心得就是刷题刷出来的。

7.3 模板与题解分离的个人习惯

最后分享一个我自己的习惯：把模板本身和用模板解的题的题解分开存放。模板库里只放“干净的”、不掺杂业务逻辑的核心算法代码，题解放带题目背景、完整判断逻辑的代码。这样每次用模板时都要自己思考怎么把题目映射到算法上，而不是机械地复制粘贴，思维能力不会退化。

图论模板这东西，看起来是背代码，实际上背的是边界条件、复杂度分析、适用场景的快速映射。把这些整理成自己的东西，才能在真正的比赛或者面试里游刃有余。