DFS
DFS 重点是 顺序，回溯问题注意复原操作
843. n−皇后问题：将 n 个皇后放在 $n×n$ 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数 n，请你输出所有的满足条件的棋子摆法。
方法一：DFS（行）+ 剪枝，按行枚举，下一行必须放子
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
35
36
37
38
39
40
41
42
|
#include <iostream>
using namespace std;
const int N = 10;
char g[N][N];
bool col[N], dg[N*2], udg[N*2]; // 对角线 dg(/), udg(\) 有 2*n-1 条
int n;
void dfs(int r) {
// 最后一行已完成，输出
if (r == n) {
for (int i = 0; i < n; i++) puts(g[i]);
puts("");
return;
}
// 当前行选择一个
for (int c = 0; c < n; c++) {
// 剪枝，其中 [c - u + n] 保证下标为正
if (!col[c] && !dg[c + r] && !udg[c - r + n]) {
g[r][c] = 'Q';
col[c] = dg[c + r] = udg[c - r + n] = true;
dfs(r + 1);
// 复原
col[c] = dg[c + r] = udg[c - r + n] = false;
g[r][c] = '.';
}
}
}
int main() {
cin >> n;
// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0);
return 0;
}
|
方法二：DFS（点）+ 剪枝，更原始的按点搜索，下一个点不一定放子
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
using namespace std;
const int N = 10;
char g[N][N];
bool row[N], col[N], dg[N*2], udg[N*2]; // 对角线 dg(/), udg(\) 有 2*n-1 条
int n;
void dfs(int r, int c, int sum) {
// 一行结束，继续下一行
if (c == n) r++, c = 0;
// 最后一行已完成，但可能不满足条件
if (r == n) {
if (sum == n) {
// 已经放置的棋子数目达到 n，输出
for (int i = 0; i < n; i++) puts(g[i]);
puts("");
}
return;
}
// 当前点不选
dfs(r, c+1, sum);
// 当前点选
// 剪枝，其中 [c - u + n] 保证下标为正
if (!row[r] && !col[c] && !dg[c + r] && !udg[c - r + n]) {
g[r][c] = 'Q';
row[r] = col[c] = dg[c + r] = udg[c - r + n] = true;
// dfs(r, c+1, sum+1);
dfs(r+1, 0, sum+1); // 优化：放子后，当前行一点不能再放子了
// 复原
row[r] = col[c] = dg[c + r] = udg[c - r + n] = false;
g[r][c] = '.';
}
}
int main() {
cin >> n;
// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0, 0, 0);
return 0;
}
|
比较按行搜索与按点搜索：
- 按行层次更高，已经从题意剥离出行互斥的信息（当然按点也可以在这方面优化）
- 落子情况和最终状态不同
- 按行每次循环保证落子，落子后再递归下一行，所以当
u = n 时一定满足要求
- 按点则可能当
x = n 时后面几行没有落子，所以要多一个参数记录落子数
- 按行搜索时间复杂度远远低于按点搜索
BFS
844. 走迷宫：给定一个 $n×m$ 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。最初，有一个人位于左上角 $(1,1)$ 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 $(n,m)$ 处，至少需要移动多少次。
数据保证 $(1,1)$ 处和 $(n,m)$ 处的数字为 0，且一定至少存在一条通路。
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <cstring> // memset
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int g[N][N], d[N][N];
int n, m;
int bfs() {
// -1 代表未访问
memset(d, -1, sizeof d);
d[0][0] = 0;
queue<PII> q;
q.push({0, 0});
while (q.size()) {
auto t = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i], y = t.second + dy[i];
// 界内 可访问 未访问
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
d[x][y] = d[t.first][t.second] + 1;
q.push({x, y});
}
}
}
return d[n - 1][m - 1];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
cout << bfs();
return 0;
}
|
845. 八数码（需要维护更复杂的状态）：在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。例如：
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <cstring> // find
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 100;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
unordered_map<string, int> d; // distance
int bfs(string start) {
string end = "12345678x";
queue<string> q;
q.push(start);
while (q.size()) {
string t = q.front(); q.pop();
int dist = d[t];
if (t == end) return dist;
for (int i = 0; i < 4; i++) {
int k = t.find('x'); // string.find(x) 返回字符 x 下标
int a = k / 3, b = k % 3;
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < 3 && y >= 0 && y < 3) {
swap(t[k], t[x*3 + y]);
if (!d.count(t)) {
// 新的局面，更新距离并加入队列
d[t] = dist + 1;
q.push(t);
}
// 注意状态恢复，继续下一个方向
swap(t[k], t[x*3 + y]);
}
}
}
return -1;
}
int main() {
string start;
for (int i = 0; i < 9; i++) {
char c;
cin >> c;
start += c;
}
cout << bfs(start);
return 0;
}
|
树、图中的 DFS
846. 树的重心：给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
每次 dfs 可以确定假设 u 为重心的最大连通块的节点数，并且更新一下 ans。即 dfs 并不直接返回答案，而是在每次更新中迭代一次答案。
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int h[N], e[N*2], ne[N*2], idx; // 无向图方式存储树，2*(n-1)条边
bool st[N]; // 防止回溯访问父节点
int n;
int ans = N; // 重心的所有子树中，最大的结点数目
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 返回以 u 为根的所有子树的节点数量总和（包括 u 自身）
int dfs(int u) {
st[u] = true;
int sum = 1; // 包含自身节点
int cnt = 0; // 如果将这个点删除后，剩余各个连通块中点数的最大值
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (!st[v]) {
int s = dfs(v);
sum += s; // 各子节点数目累加
cnt = max(cnt, s);
}
}
cnt = max(cnt, n - sum); // 父节点所在的连通块点数
ans = min(ans, cnt); // 最小的最大联通子图节点数
return sum;
}
int main() {
memset(h, -1, sizeof h);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a); // 双向便于遍历
}
// 无向图，可以从任意节点开始遍历
dfs(1);
cout << ans;
return 0;
}
|
树、图中的 BFS
847. 图中点的层次：给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。所有边的长度都是 1，点的编号为 1∼n。
请你求出 1 号点到 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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10;
int h[N], e[N], ne[N], idx;
int d[N];
int n, m;
// 添加一条边 a->b
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {
memset(d, -1, sizeof d);
queue<int> q;
q.push(1); // start from node 1
d[1] = 0;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (d[v] == -1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d[n];
}
int main() {
cin >> n >> m;
// 邻接表初始化
memset(h, -1, sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs();
return 0;
}
|
拓扑排序
848. 有向图的拓扑序列：给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
有环图不存在拓扑序列，判断存在拓扑序列等价判断是图中是否存在环
入度表法
选择入度为 0 的点作为起点，将所有入度为 0 的节点入队，并更新剩下的点的入度，若有新的节点入度为 0 则加入队列
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int h[N], e[N], ne[N], idx; // 邻接表
int q[N], hh, tt = -1; // 队列
int d[N]; // 点的入度
int n, m;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topo() {
// 所有入度为 0 的点加入队列
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
q[++tt] = i;
}
}
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int v = e[i];
d[v]--;
if (d[v] == 0) q[++tt] = v;
}
}
return tt == n - 1; // 队列中有 n 个点
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if (topo()) {
for (int i = 0; i < n; i++) cout << q[i] << ' ';
} else {
cout << -1;
}
return 0;
}
|
入度表法既可以使用 BFS 也可以使用 DFS
更多拓扑代码解法：207. 课程表（判断序列是否存在）| 210. 课程表 II（给出任意序列）
标记法
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
35
36
|
class Solution {
public:
vector<vector<int>> child; // 邻接表
vector<int> st; // 访问状态
vector<int> path;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
child.resize(numCourses);
st.resize(numCourses, 0);
// 建图
for (auto& p: prerequisites) {
int a = p[1], b = p[0]; // a->b
child[a].push_back(b);
}
// DFS
for (int i = 0; i < numCourses; i++) {
if (!dfs(i)) return {};
}
// 路径逆序
reverse(path.begin(), path.end());
return path;
}
// 0 未被 DFS 访问
// -1 其他节点启动的 DFS 访问过了，不需再访问
// 1 本节点启动的 DFS 访问过了，遇到说明有环
bool dfs(int u) {
if (st[u] == -1) return true;
if (st[u] == 1) return false;
st[u] = 1;
for (auto v: child[u]) {
if (!dfs(v)) return false;
}
st[u] = -1;
path.push_back(u);
return true;
}
};
|
最短路问题
图的表示方式：稠密图→邻接矩阵，稀疏图→邻接表（详见博客）
这里不区分有向图、无向图，均为有向图的算法，因为无向图是特殊的有向图
Dijkstra
朴素版
自环不影响最短路，重边在建图读入时选择最短的一条
849. Dijkstra求最短路 I
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
35
36
37
38
39
40
41
42
43
44
45
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, inf = 0x3f3f3f3f;
int g[N][N]; // 邻接矩阵
int dist[N]; // 1号点到 n号点的最短距离
bool st[N];
int n, m;
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i++) {
// find min dist O(n^2) total
int t = -1;
for (int j = 1; j <= n; j++) {
if (st[j]) continue;
if (t == -1 || dist[j] < dist[t]) t = j;
}
st[t] = true;
// update O(m) total
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == inf) return -1;
return dist[n];
}
int main() {
memset(g, 0x3f, sizeof g);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << dijkstra();
return 0;
}
|
堆优化版
堆的实现
- 手写堆：可直接修改制定元素，需要维护两个映射。n 个元素
O(mlgn)
- 优先队列：不能直接修改指定元素，会有冗余。m 个元素
O(mlgm)
自环不影响最短路，重边不需要处理（堆中冗余元素）
850. Dijkstra求最短路 II
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010, inf = 0x3f3f3f3f;
int h[N], e[N], w[N], ne[N], idx; // 邻接表
int dist[N]; // 1号点到 n号点的最短距离
bool st[N];
int n, m;
// 添加一条边a->b，边权为c
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 定义小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // {dist, i}
while (heap.size()) {
// find min dist O(n) total
auto t = heap.top(); heap.pop();
int u = t.second;
if (st[u]) continue; // 排除冗余
st[u] = true;
// update O(m*logn) total [实际使用优先队列 O(m*logm)]
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i], wg = w[i];
if (dist[u] + wg < dist[v]) {
dist[v] = dist[u] + wg;
heap.push({dist[v], v});
}
}
}
if (dist[n] == inf) return -1;
return dist[n];
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra();
return 0;
}
|
Bellman-Ford
853. 有边数限制的最短路：给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
边 a → b (w)
松弛操作：d[b] = min(d[b], d[a] + w)
三角不等式：d[b] ≤ d[a] + w
出发点与目标的路径中存在负权回路则无最短路径，BF 算法可检测负权回路。第 k 次迭代是不超过 k 步的最短路径，若第 n 次迭代仍有最短路更新，则说明存在 n 条边的最短路，则存在负权回路。但检测负权回路一般不用 BF 因为时间复杂度较高。
限制了路径的边数，有负环不影响。
外层 k 次迭代，得到不超过 k 条边的最短路径，内层遍历所有边。
不需要考虑点与边的关系，无脑遍历所有边，边直接用结构体数组存储。
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
35
36
37
38
39
40
41
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
int dist[N], backup[N];
int n, m, k;
struct Edge{
int a, b, w;
} edges[M];
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i ++) {
memcpy(backup, dist, sizeof dist); // 防止更新串联，备份上次迭代的数据
for (int j = 0; j < m; j ++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
}
}
return dist[n];
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < m; i ++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = bellman_ford();
if (ans > 0x3f3f3f3f / 2) puts("impossible");
else cout << ans;
return 0;
}
|
SPFA
SPFA (Shortest Path Faster Algorithm) 是 Bellman Ford 的优化版
dist[b] = min(dist[b], backup[a] + w);
当 backup[a] 变小才会更新，记录变小的 backup[a] 来选择更新
最短路径
851. spfa 求最短路：迭代过程中不对所有边遍历，只对 dist[a] 减少的点的所有出边遍历
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N]; // 点是否在队列中
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true; // 在队列中
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f) puts("impossible");
else cout << t << endl;
return 0;
}
|
判断负环
记录求最短路径时途径点的个数，当个数 ≥ n 时，说明存在负环。
不求 dist 的绝对大小，可不初始化为 inf。
dist 初始全为 0，遇到负边更新，有负环则不断绕圈，dist 不断减小。
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N], cnt[N];
bool st[N]; // 是否在队列中
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int spfa() {
queue<int> q;
for (int i = 1; i <= n; i ++) { // 从 1 出发的点经过的路径不一定含负环
q.push(i); // 初始时所有点全部加入保证一定能检测到环
st[i] = true;
}
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
if (spfa()) puts("Yes");
else puts("No");
return 0;
}
|
Floyd
dp 思路：d[k, i, j] 只经过 1~k 中的点，i → j 的最短路径
d[k, i, j] = d[k - 1, i, k] + d[k-1, k, j] → d[i, j] = d[i, k] + d[k, j]
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
35
36
37
38
39
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
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]);
}
int main() {
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
int a, b, w;
while (m--) {
scanf("%d%d%d", &a, &b, &w);
d[a][b] = min(d[a][b], w); // 重边
}
floyd();
while (Q--) {
cin >> a >> b;
if (d[a][b] > INF / 2 ) puts("impossible");
else cout << d[a][b] << endl;
}
return 0;
}
|
最小生成树
Prim
858. Prim算法求最小生成树：与 Dijkstra 类似，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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N]; // dist[] 点到集合的距离
bool st[N];
int n, m;
int prim() {
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 -1; // 存在不连通的情况
// 加入集合并更新结果，初始第一个点不加
st[t] = true;
if (i) res += dist[t];
// 跟新其他点到集合的距离
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == -1) puts("impossible");
else printf("%d\n", t);
return 0;
}
|
Kruskal
859. Kruskal算法求最小生成树：
- 对边由小至大排序
- 边的两点不在同一连通则加入，加入了 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m;
int p[N];
struct Edge{
int a, b, w;
bool operator < (const Edge &e) {
return w < e.w;
}
} edges[N];
int Find(int x) {
if (p[x] != x) p[x] = Find(p[x]);
return p[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
// 对边进行排序
sort(edges, edges + m);
for (int i = 0; i < m; i++) p[i] = i;
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = Find(a), b = Find(b);
if (a != b) {
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) puts("impossible"); // 加入 n - 1 次，加入 n - 1 条边，得到 n 个点
else cout << res;
return 0;
}
|
二分图
二分图：一条边的两个端点不在同一个集合
给定一个图是二分图，当且仅当不含奇数环
染色法
860. 染色法判定二分图：算法时间复杂度：$O(n+m)$
图中不含奇数环，在交替染色过程中不会存在染色矛盾。0 未染色 1 A 2 B
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;
int color[N];
int n, m;
// 添加一条边a->b
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
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;
// dfs(j, 3 - c);
}
else if (color[j] == c) return false;
}
return true;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
int a, b;
while (m--) {
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
bool flag = true;
// 图可能不连通
for (int i = 1; i <= n; i ++) {
if (!color[i]) {
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag) puts("Yes");
else puts("No");
return 0;
}
|
匈牙利算法
861. 二分图的最大匹配：算法时间复杂度：$O(mn)$，实际运行时间远小于 $O(mn)$
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
int n1, n2, m;
int match[N]; // 右集合的匹配
bool st[N]; // 每次搜索右集合的元素不能重复
int add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int find(int x) {
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
// 右集合的元素还没考虑过
if (!st[j]) {
st[j] = true;
// 右边 j 没有匹配 or 已经匹配 j 的左部可以找到其他右部
if (match[j] == 0 || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
cin >> n1 >> n2 >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; i++){
memset(st, false, sizeof st); // 搜索右集合的元素不能重复
if (find(i)) res ++;
}
cout << res;
return 0;
}
|
Alfly
