算法笔记:AcWing - 搜索与图论

算法笔记:AcWing - 搜索与图论

Ginkgo True love prevails.

写这篇的初衷:图论算法模板多、变种多,死记硬背很容易混淆。这篇试着从”什么时候用”和”为什么有效”两个角度重新整理,帮你建立直觉。

图论的本质:把实际问题抽象成点和边的关系,然后用搜索或贪心/动态规划来解决。


一、DFS 与 BFS:两种搜索策略

DFS 深度优先搜索 —— “一条路走到黑”

核心直觉:像一个很执着的人,选一条路一直走,走不通了再 backtrack 回来换下一条。

适用场景:

  • 枚举所有可能情况(全排列、组合)
  • 连通性问题(判断两点是否可达)
  • 树的遍历
  • 需要”回溯”的问题(八皇后、数独)

空间复杂度:,h 是递归深度(栈空间)

关键技巧:

  1. 恢复现场:回溯时要撤销之前的修改
  2. 剪枝:提前判断某条路走不通,直接返回

模板:全排列问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 10;
int n;
int path[N]; // 记录当前路径
bool st[N]; // 记录每个数是否用过

void dfs(int u) {
if (u == n) { // 走到终点,输出方案
for (int i = 0; i < n; i++) cout << path[i] << ' ';
cout << '\n';
return;
}

// 枚举下一个位置可以放哪个数
for (int i = 1; i <= n; i++) {
if (!st[i]) {
st[i] = true;
path[u] = i;
dfs(u + 1); // 递归填下一个位置
st[i] = false; // 恢复现场(回溯)
}
}
}

为什么需要恢复现场:因为 st[i] 表示”这个数在当前路径中是否被使用”,回溯后要让它能被其他分支使用。


经典例题:八皇后问题

问题:在 n×n 棋盘上放 n 个皇后,使它们互不攻击(不在同一行、列、对角线)。

思路 1:按行枚举(推荐,更快)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 20;  // 对角线最多 2n-1 条
int n;
char g[N][N];
bool col[N], dg[N], udg[N]; // 列、对角线、反对角线

void dfs(int u) { // u 表示当前处理第 u 行
if (u == n) {
for (int i = 0; i < n; i++) puts(g[i]);
cout << '\n';
return;
}

for (int i = 0; i < n; i++) {
// 剪枝:检查列、对角线、反对角线是否有冲突
// 对角线:y = x + b => b = y - x (加 n 防止负数)
// 反对角线:y = -x + b => b = x + y
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
// 恢复现场
col[i] = dg[u + i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
}

思路 2:按格子枚举(每个格子放或不放)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int x, int y, int s) {  // s 表示已放了多少皇后
if (y == n) y = 0, x++; // 换行
if (x == n) {
if (s == n) { // 放了 n 个才输出
for (int i = 0; i < n; i++) puts(g[i]);
cout << '\n';
}
return;
}

// 不放
dfs(x, y + 1, s);

// 放(需要满足条件)
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
// 恢复现场
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
}

为什么思路 1 更快:思路 1 隐含了”每行必须放一个”的先验知识,搜索空间更小。思路 2 需要枚举每个格子放或不放,复杂度更高。


BFS 宽度优先搜索 —— “广撒网”

核心直觉:像波纹一样一圈圈向外扩散,先访问离起点近的点,再访问远的点。

适用场景:

  • 最短路问题(边权为 1 时,BFS 第一次到达的点就是最短距离)
  • 层次遍历(树的层序遍历)
  • 状态空间搜索(如迷宫、拼图)

空间复杂度:,需要存一层的所有节点

关键性质:BFS 具有最短性——第一次扩展到某个点时,走的步数一定是最少的。


模板:迷宫最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N = 110;
int n, m;
int g[N][N]; // 地图,0 表示可走,1 表示障碍
int d[N][N]; // 距离数组,-1 表示未访问

int bfs() {
queue<pair<int, int>> q;
q.push({0, 0});
memset(d, -1, sizeof d);
d[0][0] = 0;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

while (!q.empty()) {
auto [x, y] = q.front();
q.pop();

// 向四个方向扩展
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
g[nx][ny] == 0 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
}
return d[n - 1][m - 1]; // 返回终点距离
}

如何记录路径?

额外开一个数组记录每个点是从哪个点扩展过来的:

1
2
3
4
5
6
7
8
9
10
11
12
pair<int, int> prev[N][N];  // 记录前驱

// BFS 中更新
prev[nx][ny] = {x, y};

// 回溯路径
int x = n - 1, y = m - 1;
while (x || y) {
cout << x << ' ' << y << '\n';
auto [px, py] = prev[x][y];
x = px, y = py;
}

BFS 与 DP 的关系

最短路问题本质上是一种 DP:

  • 状态:d[i] 表示从起点到 i 的最短距离
  • 转移:d[v] = min(d[v], d[u] + 1)
  • 无环:BFS 保证每个点只被更新一次

区别:DP 通常用于 DAG(有向无环图),而 BFS 可以处理任意无权图。


二、树与图的存储

核心概念

  • 树:无环连通图,n 个点 n-1 条边
  • 图:点 + 边的集合,分有向图和无向图
  • 无向图:可以看成每条边连了两次的有向图

存储方式对比

邻接矩阵
1
int g[N][N];  // g[i][j] = 1 表示 i->j 有边

优点:判断两点是否有边是

缺点:空间 ,适合稠密图

适用:点数较少(n ≤ 1000)的稠密图


邻接表(vector 实现)
1
2
3
4
5
6
7
8
9
10
11
12
struct Edge {
int to, w;
};
vector<vector<Edge>> gt(n + 1);

// 加边
gt[u].emplace_back(v, w);

// 遍历 u 的所有出边
for (auto& e : gt[u]) {
int v = e.to, w = e.w;
}

优点:空间 ,适合稀疏图

缺点:判断两点是否有边需要遍历


数组模拟邻接表(竞赛常用)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 100010, M = N * 2;  // 无向图边数开 2 倍
int h[N], e[M], ne[M], w[M], idx;

void init() {
memset(h, -1, sizeof h);
idx = 0;
}

void add(int u, int v, int c) {
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++;
}

// 遍历 u 的所有出边
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i], c = w[i];
}

为什么用数组模拟:

  • 避免动态内存分配,速度更快
  • 内存连续,缓存友好
  • 不会内存泄漏

链式前向星

本质上和数组模拟邻接表是一回事,只是用结构体包装了一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Edge {
int to, w, next;
} edge[M];

int head[N], idx;

void add(int u, int v, int w) {
edge[idx] = {v, w, head[u]};
head[u] = idx++;
}

// 遍历
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to, w = edge[i].w;
}

理解技巧:把 head[u] 看成链表头,next 指针把同一起点的边串起来。


树的遍历

BFS:层序遍历(从上到下一层一层访问)

DFS:

  • 前序遍历:根→左→右
  • 中序遍历:左→根→右
  • 后序遍历:左→右→根

三、树与图的 DFS

模板

1
2
3
4
5
6
7
8
9
bool st[N];  // 访问标记

void dfs(int u) {
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) dfs(j);
}
}

经典应用:树的重心

问题:删掉哪个点后,最大连通块最小?

思路:DFS 过程中计算每个子树的大小,同时更新答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, ans = N;
bool st[N];

// 返回以 u 为根的子树大小
int dfs(int u) {
st[u] = true;
int sum = 1, res = 0; // sum: 子树大小,res: 删 u 后的最大连通块

for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
int s = dfs(j);
res = max(res, s); // 子树是一个连通块
sum += s;
}
}

res = max(res, n - sum); // 上面的部分也是一个连通块
ans = min(ans, res);

return sum;
}

关键点:删掉 u 后,连通块最多有三部分:左子树、右子树、整棵树减去以 u 为根的子树。


四、树与图的 BFS

模板:求点的层次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int d[N];  // 距离/层次

int bfs() {
queue<int> q;
q.push(1);
memset(d, -1, sizeof d);
d[1] = 0;

while (!q.empty()) {
int t = q.front();
q.pop();

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) { // 未访问过
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}

适用场景:所有边权都是 1 的最短路问题


五、拓扑排序

核心概念

拓扑序列:对于有向图的每条边 (u, v),u 在序列中都出现在 v 前面。

存在条件:有向无环图(DAG) 一定存在拓扑序列

应用:

  • 任务调度(某些任务必须在其他任务之前完成)
  • 判环(如果不存在拓扑序列,说明有环)

算法思路

  1. 将所有入度为 0 的点入队
  2. 每次取出队头 t,把 t 的所有出边终点的入度 -1
  3. 如果某个点入度变为 0,入队
  4. 如果最终所有点都入队过,存在拓扑序列;否则有环

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int d[N];  // 入度
int q[N], hh = 0, tt = -1;
int res[N], cnt = 0; // 记录拓扑序

bool topsort() {
// 入度为 0 的点入队
for (int i = 1; i <= n; i++)
if (!d[i]) q[++tt] = i;

while (hh <= tt) {
int t = q[hh++];
res[cnt++] = t; // 记录拓扑序

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
d[j]--;
if (!d[j]) q[++tt] = j;
}
}

return cnt == n; // 所有点都入队过,说明无环
}

注意:拓扑序列不唯一。OJ 中对于多解的情况会用 Special Judge (SPJ) 判断。


六、最短路算法全家桶

问题分类

类型 描述 算法
单源最短路 从一个点到其他所有点 Dijkstra, Bellman-Ford, SPFA
多源汇最短路 任意两点之间的最短路 Floyd

边权情况:

  • 所有边权为正:Dijkstra
  • 存在负权边:Bellman-Ford / SPFA
  • 存在负环:最短路可能不存在

Dijkstra 算法

核心思想:贪心。每次选当前距离起点最近的点,用它更新其他点。

限制:不能有负权边(贪心不再成立)


朴素版 Dijkstra

适用:稠密图(),用邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N]; // 是否已确定最短路

int dijkstra(int n) {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < n; i++) {
// 找未确定的点中距离最小的
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

st[t] = true;

// 用 t 更新其他点
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}

return dist[n] == INF ? -1 : dist[n];
}

为什么正确:每次迭代确定一个点的最短路,n 次迭代后所有点都确定。


堆优化 Dijkstra

适用:稀疏图(),用邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];

typedef pair<int, int> PII;

int dijkstra(int n) {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // {距离,点编号}

while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();

if (st[u]) continue; // 已经确定过,跳过(去重)
st[u] = true;

for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i], c = w[i];
if (dist[v] > d + c) {
dist[v] = d + c;
heap.push({dist[v], v});
}
}
}

return dist[n] == INF ? -1 : dist[n];
}

为什么需要 st 数组:同一个点可能被多次加入堆(每次距离更新都加一次),但只有第一次弹出时是最优的。


Dijkstra vs Bellman-Ford
对比项 Dijkstra Bellman-Ford
时间复杂度 或
负权边 ❌ 不支持 ✅ 支持
稠密图性能
边数限制 无 可限制经过边数

结论:没有负权边时,Dijkstra 通常比 Bellman-Ford 快很多。


Bellman-Ford 算法

核心思想:松弛操作。对所有边进行 n-1 轮松弛,每轮尝试更新所有点。

适用场景:

  • 存在负权边
  • 限制经过的边数不超过 k(这是 SPFA 做不到的)

原理:最短路最多经过 n-1 条边(否则有环)。n-1 轮松弛后一定收敛。


模板(限制边数版)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 510, M = 10010, INF = 0x3f3f3f3f;
int n, m, k;
int dist[N], backup[N];

struct Edge {
int u, v, w;
} edges[M];

int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

for (int i = 0; i < k; i++) { // 只松弛 k 轮
memcpy(backup, dist, sizeof dist); // 备份,防止串联更新
for (int j = 0; j < m; j++) {
auto [u, v, w] = edges[j];
dist[v] = min(dist[v], backup[u] + w);
}
}

return dist[n] > INF / 2 ? -1 : dist[n]; // 考虑负权边的影响
}

为什么要备份:防止一轮中多次更新(串联)。比如 1→2→3,如果不用 backup,可能一轮中 1 更新了 2,2 又更新了 3,相当于走了两条边。


SPFA 算法

核心思想:Bellman-Ford 的优化。只有距离被更新的点,才需要去更新它的邻居。

实现:用队列维护需要更新的点

时间复杂度:平均 ,最坏

限制:不能有负环


模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N]; // 是否在队列中

int spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);
st[1] = true;

while (!q.empty()) {
int t = q.front();
q.pop();
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i], c = w[i];
if (dist[j] > dist[t] + c) {
dist[j] = dist[t] + c;
if (!st[j]) { // 不在队列中才加入
q.push(j);
st[j] = true;
}
}
}
}

return dist[n] == INF ? -1 : dist[n];
}

SPFA 被”卡”是什么意思?

可以构造特殊数据让 SPFA 退化成 ,这时候就很慢。一般遇到这种情况换堆优化 Dijkstra(如果没有负权边)。


判负环

思路:记录最短路经过的边数,如果某条路径边数 ≥ n,说明有负环。

1
2
3
4
5
6
7
8
int cnt[N];  // 记录边数

if (dist[j] > dist[t] + c) {
dist[j] = dist[t] + c;
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 存在负环
// ...
}

注意:如果要判断整个图是否存在负环(不一定是从 1 出发),需要一开始把所有点都放入队列。


Floyd 算法

核心思想:动态规划。三重循环,暴力美学。

适用:多源最短路(求任意两点间的最短距离)

时间复杂度:

限制:不能有负环(但可以处理负权边)


模板
1
2
3
4
5
6
7
8
9
10
const int N = 210, INF = 0x3f3f3f3f;
int n, m, Q;
int d[N][N]; // d[i][j]: i 到 j 的最短距离

void floyd() {
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]);
}

DP 解释:

  • 状态:d[k][i][j] 表示从 i 到 j,只经过 1~k 这些中间点的最短距离
  • 转移:d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])
  • 优化:第一维可以省略

七、最小生成树

问题描述

场景:n 个城市,m 条可选道路,选 n-1 条路使所有城市连通且总代价最小。

前提:无向图,边权可正可负


Prim 算法

核心思想:类似 Dijkstra。维护一个”已选点集合”,每次选距离集合最近的点加入。


朴素版 Prim

适用:稠密图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N];

int prim(int n) {
memset(dist, 0x3f, sizeof dist);
int res = 0;

for (int i = 0; i < n; i++) {
// 找集合外距离最近的点
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if (i && dist[t] == INF) return INF; // 不连通
if (i) res += dist[t];

// 用 t 更新其他点到集合的距离
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], g[t][j]);

st[t] = true;
}

return res;
}

和 Dijkstra 的区别:dist[j] 的含义不同。Dijkstra 是”到起点的距离”,Prim 是”到已选集合的距离”。


堆优化 Prim

适用:稀疏图(但一般不常用,Kruskal 更简单)


Kruskal 算法

核心思想:贪心。把所有边从小到大排序,依次选边,如果边的两端不连通就加入。

时间复杂度:(排序的复杂度)

适用:稀疏图


模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N = 100010, M = 200010;
int n, m;
int p[N]; // 并查集

struct Edge {
int a, b, w;
bool operator<(const Edge& W) const {
return w < W.w;
}
} edges[M];

int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal() {
sort(edges, edges + m);

for (int i = 1; i <= n; i++) p[i] = i;

int res = 0, cnt = 0;
for (int i = 0; i < m; i++) {
auto [a, b, w] = edges[i];
a = find(a), b = find(b);
if (a != b) { // 不连通
p[a] = b;
res += w;
cnt++;
}
}

return cnt < n - 1 ? INF : res; // 边数不足 n-1,不连通
}

Prim vs Kruskal
对比项 Prim Kruskal
时间复杂度 或
稠密图 ✅ 更优 ❌ 排序开销大
稀疏图 ❌ ✅ 更优
实现难度 中等 简单(需要并查集)

建议:稀疏图用 Kruskal,稠密图用 Prim。


八、二分图

核心概念

二分图:可以把所有点分成两组,所有边都只连接不同组的点。

判定定理:一个图是二分图 当且仅当 图中不含奇数环


染色法判定

思路:用 DFS 给每个点染色(1 或 2),相邻点颜色必须不同。如果出现冲突,不是二分图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 100010, M = 200010;
int h[N], e[M], ne[M], idx;
int color[N]; // 0: 未染色,1/2: 颜色

bool dfs(int u, int c) {
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!color[j]) {
if (!dfs(j, 3 - c)) return false; // 染相反颜色
} else if (color[j] == c) return false; // 冲突
}
return true;
}

// 主函数
bool is_bipartite = true;
for (int i = 1; i <= n; i++)
if (!color[i] && !dfs(i, 1)) {
is_bipartite = false;
break;
}

为什么是 3-c:c 是 1 或 2,3-c 就是相反的颜色。


匈牙利算法

问题:求二分图的最大匹配(最多能配多少对)

时间复杂度:,但实际运行远小于这个上界

核心思想:贪心 + 回溯。”待字闺中,据为己有;名花有主,求他放手。”


模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
int match[N]; // match[j]: j 的匹配对象
bool st[N]; // 每轮 DFS 的访问标记

bool find(int x) {
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
// j 未匹配,或者能让 j 的原配找到新欢
if (!match[j] || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}

// 主函数
int res = 0;
for (int i = 1; i <= n1; i++) {
memset(st, false, sizeof st);
if (find(i)) res++;
}

st[] 的作用:防止一轮 DFS 中重复访问同一个点。每轮开始前要清空。


经典例题:棋盘覆盖

问题:N×N 棋盘,某些格子禁止放置。求最多能放多少个 1×2 的骨牌。

建模:

  • 每个格子是一个点
  • 相邻格子连边
  • 问题转化为:选最多的不相交边 → 最大匹配

二分图构造:按 (i + j) % 2 分组,相邻格子一定在不同组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N = 110;
bool ban[N][N];
int h[N * N], e[N * N * 4], ne[N * N], idx;
int match[N * N];
bool st[N * N];

int get(int x, int y) {
return (x - 1) * N + y; // 二维转一维
}

// 建图
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (ban[i][j]) continue;
if ((i + j) % 2 == 0) { // 只从一侧连边
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
for (int k = 0; k < 4; k++) {
int ni = i + dx[k], nj = j + dy[k];
if (ni >= 1 && ni <= n && nj >= 1 && nj <= n && !ban[ni][nj])
add(get(i, j), get(ni, nj));
}
}
}
}

// 跑匈牙利
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if ((i + j) % 2 == 0 && !ban[i][j]) {
memset(st, false, sizeof st);
if (find(get(i, j))) res++;
}

小结:图论算法选择指南

问题类型 推荐算法 时间复杂度
枚举所有方案 DFS + 回溯 指数级
无权图最短路 BFS
有向无环图排序 拓扑排序
单源最短路(正权) Dijkstra(堆优化)
单源最短路(负权) SPFA / Bellman-Ford 平均
限制边数的最短路 Bellman-Ford
多源最短路 Floyd
最小生成树(稠密) Prim
最小生成树(稀疏) Kruskal
二分图判定 染色法
二分图最大匹配 匈牙利算法

最后提醒:图论算法的核心是建模——把实际问题抽象成点和边的关系。模板好背,建模难练,多做题多思考才是王道。

  • Title: 算法笔记:AcWing - 搜索与图论
  • Author: Ginkgo
  • Created at : 2026-04-11 11:30:00
  • Updated at : 2026-04-12 16:22:27
  • Link: https://g1nkgo7.github.io/2026/04/11/算法笔记-AcWing-搜索与图论/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments