AcWing 搜索与图论章节笔记

这一章的主线是“建模 -> 存图 -> 选算法”。很多题目代码不复杂，难的是第一步选对方法。

本章核心模板

DFS / 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfs(int u) {
    if (u > n) {
        // 输出答案
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
queue<pair<int,int>> q;
q.push({0, 0});
dist[0][0] = 0;

while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 0 && dist[a][b] == -1) {
            dist[a][b] = dist[x][y] + 1;
            q.push({a, b});
        }
    }
}

邻接表

1
2
3
4
5
int h[N], e[M], ne[M], w[M], idx;

void add(int a, int b, int c = 1) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> heap;
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
heap.push({0, 1});

while (!heap.empty()) {
    auto [d, ver] = heap.top();
    heap.pop();
    if (st[ver]) continue;
    st[ver] = true;
    for (int i = h[ver]; i != -1; i = ne[i]) {
        int j = e[i];
        if (dist[j] > d + w[i]) {
            dist[j] = d + w[i];
            heap.push({dist[j], j});
        }
    }
}

Bellman-Ford / SPFA

1
2
3
4
5
6
7
for (int i = 0; i < k; i++) {
    memcpy(backup, dist, sizeof dist);
    for (int j = 0; j < m; j++) {
        auto [a, b, c] = edges[j];
        dist[b] = min(dist[b], backup[a] + c);
    }
}

Floyd

1
2
3
4
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Kruskal / 染色法 / 匈牙利

1
2
3
4
5
6
7
8
sort(edges.begin(), edges.end());
for (auto [w, a, b] : edges) {
    a = find(a), b = find(b);
    if (a != b) {
        p[a] = b;
        res += w;
    }
}

本章题目与题解要点

DFS

BFS

  • 844 走迷宫：无权最短路，BFS 分层推进。
  • 845 八数码：状态图最短路，用字符串编码状态并配合哈希判重。

树与图遍历

拓扑排序

Dijkstra

Bellman-Ford / SPFA

Floyd

最小生成树

二分图

这一章怎么复习

  1. 把 844、848、850、859 四题作为本章的四个主模板。
  2. 再做 845、853、861，看自己是否真的理解状态图、边数限制和增广路。
  3. 复习时先按“无权图 / 有权图 / 最小生成树 / 二分图”分类，而不是按题号背。

返回导航