算法总结

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

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。

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. 还没学的（预告）

• 0413 最小生成树：Kruskal（并查集 + 排序）和 Prim（每次挑最近的，像 Dijkstra）。
• 0414 二分：答案有单调性时，把「求最优」变成「判对错」。手写骨架：while (l < r) { mid; if (ok(mid)) r = mid; else l = mid + 1; }
• 0415 前缀和 / 差分 / 单调栈：区间和先预处理；区间加用差分；找「左边第一个更小的」用单调栈。
• 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 速查 · 刷题清单 · 返回资源列表