算法总结

截至 0417（字符串匹配 KMP）。学到哪写到哪 —— 这张表回答一个问题：看到一道题，我该抓哪个工具？每个工具给「什么时候用、多快、代码骨架、踩过的坑」，细节点回对应课件。

1. 一张总表

2. 数据结构怎么挑

3. 图怎么存

// 有权图的邻接表（最常用）
vector<vector<pair<int,int>>> g(n + 1);   // g[u] = {v, w}
g[u].push_back({v, w});
for (auto [v, w] : g[u]) { /* 遍历 u 的出边 */ }

注意 P3385 那类题：「w ≥ 0 表示双向边，w < 0 只有单向」，一条输入可能要 push 两次。

4. 遍历：BFS / DFS

两者都是 O(n + m)，区别只在「先扩一圈」还是「先钻到底」。

// BFS：d[v] = 起点到 v 的最少边数
void bfs(int s, const vector<vector<int>>& g, vector<int>& d) {
    queue<int> q;
    d[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u])
            if (d[v] == -1) {           // 没访问过才进来
                d[v] = d[u] + 1;
                q.push(v);              // 入队前就标记（d[v] 已经不等于 -1）
            }
    }
}

// DFS：标记连通块
void dfs(int u, const vector<vector<int>>& g, vector<bool>& vis) {
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v]) dfs(v, g, vis);
}

实测（图：1→2、1→3、2→4、3→4，起点 1）：d1=0 d2=1 d3=1 d4=2，DFS 访问 4 个点。

5. 拓扑排序

什么时候能用：有向图、没有环（DAG）。典型题面是「先修课」「任务依赖」「谁必须在谁前面」。

// Kahn 算法：反复取出入度为 0 的点
vector<int> topoSort(int n, const vector<vector<int>>& g) {
    vector<int> deg(n + 1, 0), res;
    for (int u = 1; u <= n; u++)
        for (int v : g[u]) deg[v]++;              // 统计入度
    queue<int> q;
    for (int i = 1; i <= n; i++) if (deg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res.push_back(u);
        for (int v : g[u])
            if (--deg[v] == 0) q.push(v);         // 前置都做完了，可以入队
    }
    return res;
}

顺手判环：如果 res.size() != n，说明剩下的点互相依赖 —— 图里有环。
实测（同上那张图）：输出 1 2 3 4。

6. 并查集

什么时候用：题目只问「两个点在不在同一个连通块」「把两个集合并起来」，从不问你路径长什么样。加了路径压缩之后，单次操作几乎 O(1)。

int findRoot(vector<int>& fa, int x) {
    return fa[x] == x ? x : fa[x] = findRoot(fa, fa[x]);   // 路径压缩
}
void unite(vector<int>& fa, int a, int b) {
    a = findRoot(fa, a); b = findRoot(fa, b);
    if (a != b) fa[a] = b;
}

// 初始化：每个点自成一个集合
vector<int> fa(n + 1);
iota(fa.begin(), fa.end(), 0);        // fa[i] = i

两种优化别混：路径压缩（把链拍平）和按秩/按大小合并（小的挂到大的下面）。后者写错不会错答案，只会慢 —— 0410 那题里很多人写成「比较根的编号」，就是这个坑。
实测：unite(1,2)、unite(2,3) 之后，1 和 3 同根、1 和 4 不同根。

7. 最短路三兄弟

// Dijkstra：堆里存 {距离, 点}，小的先出
vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& g, int s) {
    const long long INF = 4e18;
    vector<long long> dis(n + 1, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dis[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > dis[u]) continue;                 // 懒删除：这是旧快照
        for (auto [v, w] : g[u])
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});              // 只压入，不修改堆里的旧值
            }
    }
    return dis;
}

// Bellman-Ford：不盖章，全体边松弛 n-1 轮；第 n 轮还能改 → 负环
bool bellmanFord(int n, const vector<Edge>& edges, int s, vector<long long>& dis) {
    const long long INF = 4e18;
    dis.assign(n + 1, INF);
    dis[s] = 0;
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (auto& e : edges) {
            if (dis[e.u] == INF) continue;         // 不可达的点不能拿去加
            if (dis[e.u] + e.w < dis[e.v]) { dis[e.v] = dis[e.u] + e.w; changed = true; }
        }
        if (!changed) break;                       // 整轮没变化就收工
    }
    for (auto& e : edges)
        if (dis[e.u] != INF && dis[e.u] + e.w < dis[e.v]) return false;   // 有负环
    return true;
}

// SPFA：Bellman-Ford 的队列版，用「路径边数 ≥ n」判负环
bool spfa(int n, const vector<vector<pair<int,int>>>& g, int s, vector<long long>& dis) {
    const long long INF = 4e18;
    dis.assign(n + 1, INF);
    vector<int> cnt(n + 1, 0);
    vector<bool> inq(n + 1, false);
    deque<int> q;
    dis[s] = 0; q.push_back(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop_front(); inq[u] = false;
        for (auto [v, w] : g[u])
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return false;     // 绕了 n 条边还在变短 → 负环
                if (!inq[v]) { q.push_back(v); inq[v] = true; }
            }
    }
    return true;
}

// Floyd：k 是最外层（DP 的阶段），不能换位置
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++) {
        if (f[i][k] == INF) continue;              // 省掉一半加法，也防溢出
        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];
    }

实测（1→2=2、2→3=2、2→4=1、1→3=5、3→4=3、1→4=4，从 1 出发）：四种算法给出的距离都是 0 2 4 3，d(1,4)=3。

7.5 最小生成树：Kruskal / Prim（0413）

问题换成「把所有点连通，总权最小」。它不怕负权、不怕负环，因为两种算法本质都是「按权从小到大试」。

// ① Kruskal：排序 + 并查集（最常用，只要边表）
sort(es.begin(), es.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
DSU d(n);
long long sum = 0; int used = 0;
for (auto& e : es) {
    if (d.unite(e.u, e.v)) {          // 不同根 = 不会成环，选它
        sum += e.w;
        if (++used == n - 1) break;   // 凑够 n-1 条就停
    }
}
// used < n - 1 → 图不连通（P3366 输出 orz）

// ② Prim：和 Dijkstra 只差一行 —— dis[v] = w，不是 dis[u] + w
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (used[u]) continue;
    used[u] = true; sum += d; cnt++;   // 这条边把它连进树
    for (auto [v, w] : g[u])
        if (!used[v] && w < dis[v]) { dis[v] = w; pq.push({w, v}); }
}
// cnt < n → 不连通

实测（n = 5000、m = 2×10⁵）：Kruskal 10.5 ms / Prim(堆) 4.1 ms，答案都是 762963；稠密图 n = 500 完全图：Kruskal 7.0 ms，Prim 朴素 0.7 ms。稀疏 Kruskal 顺手，稠密 Prim 朴素最快。

7.6 前缀和 / 差分 / 单调栈（0415）

三件「预处理」小工具，共同点是把一次性的 O(n²) 摊成「预处理一遍 + 之后 O(1)」。

// ① 前缀和：区间 [l, r] 的和，O(1)
s[0] = 0;
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];   // s 开 long long
long long sum = s[r] - s[l - 1];                        // 减 l-1，不是 l

// 取模变体（P3131）：同一余数之间的那段，和被模数整除
first[0] = 0;                                           // 别忘了这一行
pre = (pre + a[i]) % 7;
if (first[pre] == -1) first[pre] = i;
else best = max(best, i - first[pre]);

// ② 差分：区间 [x, y] 加 z，O(1)；最后一遍前缀和还原
for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
d[x] += z; d[y + 1] -= z;                               // d 要开到 n+2
int cur = 0;
for (int i = 1; i <= n; i++) { cur += d[i]; /* 此时 cur 就是 a[i] */ }

// ③ 单调栈：右边第一个严格更大的下标（没有则 0），从右往左扫
vector<int> f(n + 1, 0), st;
for (int i = n; i >= 1; i--) {
    while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
    f[i] = st.empty() ? 0 : st.back();                  // 求「更小」就把 <= 改成 >=
    st.push_back(i);
}

实测：P3131（n = 50000）0.20 ms；P2367（n = 5×10⁶、p = 5×10⁶）差分 75.5 ms，而朴素做法在 n = 10⁵ 就要 257 ms（差分 0.28 ms）；P5788（n = 3×10⁶）23.4 ms。每个元素进出栈各一次，所以单调栈的 while 摊还是 O(1)。

7.7 KMP（0417）

// ① pi 数组：pi[i] = s[0..i] 的最长 border 长度
vector<int> pi(m, 0);
for (int i = 1; i < m; i++) {
    int j = pi[i - 1];
    while (j > 0 && s2[i] != s2[j]) j = pi[j - 1];
    if (s2[i] == s2[j]) j++;
    pi[i] = j;
}

// ② 匹配：i 只前进，失配只退 j
int j = 0;
for (int i = 0; i < n; i++) {
    while (j > 0 && s1[i] != s2[j]) j = pi[j - 1];
    if (s1[i] == s2[j]) j++;
    if (j == m) {
        // i - m + 2 是 1-based 的出现位置
        j = pi[j - 1];              // 关键：回退才能找重叠的下一个
    }
}

实测（n1 = 10⁶，最坏数据「999 个 A + 一个 B」）：KMP 1.6 ms vs 暴力 247 ms；固定 n1、把 n2 从 500 加到 8000，暴力从 126 ms 涨到 1885 ms，KMP 一直在 1.5–1.9 ms。复杂度 O(n+m) 的来源：j 每次回退都严格变小，回退总次数 ≤ 增加总次数 = O(m)。

8. 排序

sort(a.begin(), a.end());                        // 升序
sort(a.begin(), a.end(), greater<int>());        // 降序

// 多关键字：先按第一个降序，再按第二个升序
sort(a.begin(), a.end(), [](const P& x, const P& y) {
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
});

// 要稳定排序用 stable_sort（相等元素保持原来的相对顺序）

优先队列是「堆」不是「排序」：只保证队首是极值，其余元素内部无序。要全部有序还是得 sort。

9. 还没学的（预告）

• 0416 哈希表：把「找某个值在不在」从 O(n) 压到接近 O(1)；unordered_map 会被卡，需要时用 map 或手写哈希（已出课件：0416 哈希表）。
• 0418 贪心专题：每一步取当前最优，再用交换论证证明「任意最优解都能换成贪心解且不变差」。配 P4995 / P1223。
• 0419–0421 动态规划：先想状态，再想转移，最后想边界。今天的最短路其实是 DP 的近亲（dis[v] = min(dis[v], dis[u] + w)）。

10. 易错清单

1. INF 相加溢出：INT_MAX + INT_MAX 变负数，比任何距离都小 → 用 0x3f3f3f3f 或加 >= INF 判断。
2. 多测不清空：dis / vis / 邻接表每组重建，P3385 是典型。
3. 忘记快读两行：ios::sync_with_stdio(false); cin.tie(nullptr); —— 实测 10 万点读入从 351.9 ms 降到 33.9 ms。
4. 该 long long 用了 int：距离累加、乘积、坐标平方和（P3958 就栽在这）。
5. BFS 标记写在出队时：同一个点会被重复入队，最坏变慢但不至于错；写在入队时最稳。
6. Dijkstra 忘了懒删除：if (du > dis[u]) continue;，不然一堆过期快照照样往外松弛。
7. Floyd 的 k 没放最外层：换位置能过样例，真出错（实测给出 10，真值 3）。
8. 并查集没初始化：fa[i] = i，忘了就是全域乱连。
9. 拓扑排序不看环：res.size() != n 说明有环，别把残缺顺序当答案输出。
10. 重边只留一条：多测/多边题里，后写的边会覆盖前面的（P3371 那个邻接矩阵版本的坑）。

附：复杂度与 n 的对照

这张表是经验值，常数因子差很多：同样的 O(n log n)，手写堆和 std::sort 能差几倍。看题目限制时留一倍余量。

对应课件：0408 图的遍历 · 0409 连通性与拓扑排序 · 0410 并查集 · 0411 最短路 I · 0412 最短路 II · STL 速查 · 刷题清单 · 返回资源列表