ARTICLE · 1228977

CSP-J/S 2026 :图论,模板打熟就是白送的分

发布时间：2026-10-22 15:37:42 最近访问：2026-10-22 15:37:29

10 月 31 日（周六）上午 8:30，CSP-J/S 2026 第二轮开考。

一、考到哪，先划边界

CSP-J 的图论基本只考四样：最短路（Dijkstra / Floyd）、并查集、最小生成树、拓扑排序，规模通常是 n ≤ 1000、m ≤ 10⁵，无负边权。CSP-S 再加负边权（SPFA）、二分图染色、树上差分。

九天内，J 组选手只需把前四个模板打到能默写，S 组选手加一个 SPFA。其余的等考完再说。

二、存图：别用链式前向星

链式前向星四个数组又长又易错，考场上用 `vector` 邻接表就够，对 10⁵ 完全不慢：

cpp

struct Edge { int to, w; };
vector<Edge> g[N];
void add(int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});   // 无向图才加这行
}

无向图记得加反向边，有向图一定不要加——这是图论题最常见的第一个 WA。

三、Dijkstra：复赛最常考的一个

单源最短路，边权非负。核心：每次取出当前距离最小的点，用它松弛邻居。

cpp

const long long INF = 1e18;
long long dis[N]; bool vis[N];
void dijkstra(int s, int n) {
    for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false;
    priority_queue<pair<long long,int>,
        vector<pair<long long,int>>, greater<>> pq;
    dis[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;        // 关键：弹出时判
        vis[u] = true;
        for (auto e : g[u])
            if (dis[e.to] > d + e.w) {
                dis[e.to] = d + e.w;
                pq.push({dis[e.to], e.to});
            }
    }
}

四个必踩的坑：

•`dis` 必须 `long long`，`INF` 设 `1e18`。设成 0x3f3f3f3f 加两次就溢出成负数。

•`vis` 在弹出时判断，不是入堆时，否则漏掉更优更新。

•pair 里距离在前，greater 才按距离排序，写成 {点, 距离} 直接错。

四、Floyd：点少时的万能解

多源最短路，n ≤ 300 直接上：

cpp

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

`k` 必须在最外层——唯一不能动的地方，写错顺序样例都常常能过。初始化 f[i][i] = 0、其余 INF，`f[i][i]=0` 忘写，答案会莫名偏大。

有负边权才换 SPFA，判负环加个入队计数、超过 n 次即有环。CSP-J 几乎不考；S 组无负边且 m 大时直接 Dijkstra，别赌 SPFA 不被卡。

五、并查集：两行，错一行全错

cpp

int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int a, int b) { fa[find(a)] = find(b); }

fa[x] = find(fa[x]) 里的赋值是路径压缩，漏掉复杂度退化成 O(n)，10⁵ 次操作直接超时。初始化必须 for (int i = 1; i <= n; i++) fa[i] = i;，忘了初始化，所有点全指向 0。

六、最小生成树：Kruskal = 排序 + 并查集

按边权从小到大试，能连就连，用并查集判环：

cpp

sort(e + 1, e + m + 1, [](Edge a, Edge b) { return a.w < b.w; });
int cnt = 0; long long ans = 0;
for (int i = 1; i <= m; i++) {
    if (find(e[i].u) == find(e[i].v)) continue;  // 已连通，加边成环
    merge(e[i].u, e[i].v);
    ans += e[i].w;
    if (++cnt == n - 1) break;
}
if (cnt < n - 1) puts("-1");   // 图不连通

判据一句话：选满 n-1 条边才是树，选不满就是图不连通。最后这个 if 是很多题的第二个得分点。

七、拓扑排序：顺便判有环

统计入度，入度为 0 的入队，出队时把邻居入度减一：

cpp

for (int i = 1; i <= n; i++) if (!in[i]) q.push(i);
while (!q.empty()) {
    int u = q.front(); q.pop(); ans.push_back(u);
    for (int v : g[u]) if (--in[v] == 0) q.push(v);
}
if ((int)ans.size() < n) puts("有环");   // 有环就排不完

判环只看最后排出的点数是否为 n。"任务调度""课程表"类题反复考这一招。

八、图论题的五个通用坑

1.多组数据不清空图：g[i].clear() 漏了，第二组带着第一组的边跑。

2.重边与自环：Dijkstra 能自然处理重边；Floyd 遇负权自环会出错，建图特判 u == v。

3.INF 相加溢出：INF + INF 必须仍在 long long 内，所以用 1e18 而不是 LLONG_MAX。

4.节点编号从 0 还是 1：题目给 0 到 n-1 时数组循环全要跟着改，统一转成 1-based 最省事。

5.无向图边数组开两倍：m 条无向边占 2m 个位置，开小了直接 RE。

九、今天 30 分钟

1.8 分钟：合上文章默写 Dijkstra 堆优化，对照第三节逐字检查 vis 位置和 long long。

2.7 分钟：默写并查集 find，确认有 fa[x] = find(fa[x])。

3.15 分钟：洛谷 P4779 单源最短路、P3366 最小生成树，各限时 7 分钟 AC。

本期小结

•J 组图论只考四样：最短路、并查集、最小生成树、拓扑排序

•存图用 vector 邻接表；无向图加反向边，有向图不加

•Dijkstra：dis 用 long long、INF=1e18、vis 弹出时判

•Floyd 的 k 必须在最外层，f[i][i]=0 不能忘

•Kruskal = 排序 + 并查集，选满 n-1 条边才算成功

有问题在评论区留言，吕老师每天回复。