搜索
DFS
一般和栈和递归联系起来
深度优先遍历，即优先向树底遍历，走一条路的底部，再返回走其他分支，重复步骤直到遍历全部节点
本质上是一种暴力的遍历方式，实现它不难，难在优化
阶乘
斐波那契
树遍历
树的重心
只要穷举比较每一个点的最大子树中的结点数，就可以找到最小的答案了
因此，问题化为如何求所有点最大子树的结点数，其实这个过程就是去 dfs(也是在穷举)
因此两个步骤和起来写:
- 穷举点的过程计算最大子树结点数
- 同时比较得出最小的那个数
即只要遍历完所有的点，答案就会出来了
关于遍历: 树的问题可以转换为图的问题解决，但是我们不知道树的根在哪，因此建边的时候需要建双向边，这样可以任意指定一个点作为根，而遍历树时每个点我们只走一次，因此还需要用
st标识我们已经走过的点，使遍历变成单向的。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 5, M = N << 1;
int h[N], e[M], ne[M], idx;
char st[N];
int ans = N, n;
void add(int a, int b) {
e[idx] = b,
ne[idx] = h[a],
h[a] = idx ++;
}
int dfs(int u) {
int res = 0, sum = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true; // 防止循环访问
int s = dfs(j);
sum += s;
res=max(res, s);
}
}
res=max(n-sum, res);
ans=min(res, ans);
return sum;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
全排序的枚举
这个很简单， 可以用数组表示状态，因为状态比较简单，也可以用位来表示状态
#include <iostream>
using namespace std;
const int N = 10;
int res[N];
int n;
void dfs(int u, int status) {
if (u == n) {
for (int i = 0; i < n; ++ i) printf("%d ", res[i]);
puts("");
return;
}
for (int i = 0; i < n ; ++ i)
if (!(status >> i & 1)) {
res[u] = i + 1;
dfs(u + 1, status + (1 << i));
}
}
int main() {
cin >> n;
dfs(0, 0);
}
组合的枚举
回溯
剪枝
n 皇后
经典的问题，给n x n 的国际象棋盘，问摆满皇后(它们不能相互攻击到)，有几种摆法
国家象棋中，皇后能直线攻击，即能够横竖斜攻击，因此摆放皇后时任意一条横、竖、斜线只能放一个皇后
纯枚举，不使用剪枝：
按行枚举，分支为列数，即表示某行某列是否放置棋子
#include <iostream>
using namespace std;
const int N = 12;
char g[N][N], col[N], udg[N << 1], dg[N << 1];
int n;
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; ++ i) puts(g[i]);
puts("");
return;
}
for (int i = 0; i < n; ++ i)
if (!col[i] && !dg[u + i] && !udg[u - i + n]){
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[u - i + n] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[u - i + n] = false;
g[u][i] = '.';
}
}
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;
}
```
按格子位置枚举，分支为放或不放
```cpp
#include <iostream>
using namespace std;
const int N = 12;
char g[N][N], dg[N << 1], udg[N << 1], col[N], row[N];
int n;
void dfs(int x, int y, int u) {
if (x == n) x = 0, y ++;
if (y == n) {
// 走到终点，且选了n个
if (u == n) {
for (int i = 0; i < n; ++ i) puts(g[i]);
puts("");
}
return;
}
// 不放的情况
g[y][x] = '.';
dfs(x + 1, y, u);
// 放的情况
if (!row[y] && !col[x] && !dg[x + y] && !udg[y - x + n]){
g[y][x] = 'Q';
col[x] = row[y] = dg[x + y] = udg[y - x + n] = true;
dfs(x + 1, y, u + 1);
col[x] = row[y] = dg[x + y] = udg[y - x + n] = false;
g[y][x] = '.';
}
}
int main(){
cin >> n;
dfs(0, 0, 0);
return 0;
}
关于对角线的
index，因为棋盘是正方形的所以每条对角线的斜率都为1不用考虑， 因此可以使用在坐标轴上的截距，来区别不同的对角线，反对角线:b_ = y + x，正对角线:b = y - x + n加 n 是为了防止截距出现负数
数独求解
BFS
一般和队列联系在一起
宽度优先搜索，即优先搜索节点的全部子节点，一圈一圈地遍历。 把队列的首元素弹出，把其把子节点放入队列中，重复步骤直到遍历全部节点
最短路
走迷宫
给 n x m 的地图，1 表示不能通过，0 表示能通过
问从左上角到右下角最短路径
用数组 d 表示从起点到某点的最短路径，那么能够到达某点的上一点的最短路径+1就得到该点到起点的最短路径。 因为 bfs 是一层一层遍历的，因此对于同一个点，先遍历得到的路径长度一定比后遍历得到的路径短， 所以如果 d 已经有值，那么无需更新了。
手写队列:
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 105;
int g[N][N], d[N][N];
PII q[N * N];
int n, m;
int hh = 0, tt = -1;
int bfs() {
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
memset(d, -1, sizeof d);
q[++ tt] = {0, 0};
d[0][0] = 0;
while (hh <= tt){
auto t = q[hh ++];
for (int i = 0; i < 4; ++ i) {
int x = t.first + dx[i], y = t.second + dy[i];
if (x < m && x >= 0 && y < n && y >= 0 && d[y][x] == -1 && !g[y][x]) {
d[y][x] = d[t.second][t.first] + 1;
q[++ tt] = {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() << endl;
return 0;
}
STL:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 105;
int g[N][N], d[N][N];
queue<PII> q;
int n, m;
int bfs() {
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
memset(d, -1, sizeof d);
q.push({0, 0});
d[0][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 < m && x >= 0 && y < n && y >= 0 && d[y][x] == -1 && !g[y][x]) {
d[y][x] = d[t.second][t.first] + 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() << endl;
return 0;
}
八数码
给定一个八字码，x 表示空位(即可以移动的格子)，输出把八字码还原(即没有逆序对，依次递增)的最少移动的次数 ，若无法还原输出 -1
数列的逆序数是奇数时，八字码无解，证明略
// 把上面还原为下面
2 3 4
1 5 x
7 6 8
1 2 3
4 5 6
7 8 x
其实还是最短路径问题，且可以使用bfs暴力求解，我们可以把一个数列当成一个状态(树的一个节点)，x 上下左右交换作为转移(树的分支)，那么可以知道，只要能遍历到12345678x的状态，就可以得到最少移动次数, 即转换为最短路径问题。
同样，bfs 是一层一层遍历的，因此先到达状态的路径是最短的，后续再次到达该状态无需更新
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string st){
queue<string> q;
unordered_map<string,int> d;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
q.push(st);
d[st] = 0;
string end = "12345678x";
while (q.size()) {
auto t = q.front();
q.pop();
if (t == end) return d[t];
int pos = t.find('x');
int x = pos % 3, y = pos / 3;
int dist = d[t];
for (int i = 0; i < 4 ; ++ i) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) {
swap(t[y * 3 + x], t[b * 3 + a]);
if (!d.count(t)) { // 是否已经遍历过该状态了
d[t] = dist + 1;
q.push(t);
}
swap(t[y * 3 + x], t[b * 3 + a]);
}
}
}
return -1;
}
int main(){
string st;
for (int i = 0; i < 9; i ++){
char op;
cin >> op;
st += op;
}
cout << bfs(st) << endl;
return 0;
}
Dijkstra
依次选取离出发点距离最近的点去更新其他点到出发点的距离，将选过的点加入集合，当全部点加入集合后，即可结束，此时各个点到出发点的距离就是最短距离，各个点加入集合的顺序就是最短距离的出发顺序。
不严谨证明
结论：
每一次选入集合的点都是上个点或上若干个点（起点到该点的路径已经最短）到它能抵达的点中最小距离的点(最小+最小)，因此起点到这点的路径也是最短的。
即：
O 点（起点）到 A 点已经是最小的，因此如果从 O 点到 A 点再到 B 点，是目前 O 点到所有未加入集合点中路径最小的，那么 O 点到 B 点的距离是最小的
条件：
- A 能更新 B(到达)
- OB 是目前能选出的最小边
证明：
- 有一个等式：
( 表示 X 点到 Y 点的最小距离。 )
注意这里的前提: B 被 A 更新了;
如果在 A 之前存在某点 X 使 那 B 就不会被 A 更新;
那在 A 之后呢？更不可能了，由 A 更新出来的点距离肯定比 A 小嘛(更新的更新更小)，所以上面的等式是恒成立的
又因为 B 点是 A 点能到达点中距离最小点，因此可以得到
则可证：
那为什么 B 点是 A 点能到达点中距离最小点 ?
因为 B 点到 O 点的距离是由 A 点更新来的，而在所有被 A 点更新或没更新的点中，B 到 O 点的距离是最小的(条件 2)，那么可以说明 A 点更新到的点中，A 点到 B 的距离也是最短的
证明结束
我也知道证明很烂，只是为了简单记个结论 🐷
btw，我发现 bfs 的最小路径问题，基本都有的结论：
- 最小 = 最小 + 最小
- 先到达的值小于后到达的值
因为每次选取最小距离都需要遍历一遍未加入集合的点距离，朴素版的 dijkstra 的速度被限制到
注意：
- dijkstra 算法不能在边权为负数的情况下使用
- dijkstra 算法仅能得到初始点到各点的最小距离
步骤：
- scan（找出集合外距离初始点最近的点）（可优化）
- add（将该点加入集合）
- updata（更新未加入集合各点到该点的距离）
复杂度：
- 时间：
- 空间：
- 稀疏图：
- 稠密图：
关于如何判图像的疏密，一般来说
n^2 >> m为稀疏
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
int g[N][N];
bool st[N];
int dist[N];
int n, m;
int dijkstra(){
memset(dist, 0x3f , sizeof dist); //初始化距离为无穷
dist[1] = 0;
for (int i = 0 ; i < n ; i ++){ //n 次循环，每次将一个点加入集合
int t = -1;
for (int j = 1; j <= n ; j ++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j; //选出未加入集合中最近的点
st[t] = true; //加入集合
for (int j = 1 ; j <= n ; j ++){ //用该点更新其他未加入集合中的点距离
if (!st[j]) //因为最短的距离会先被选取，因此，选取过的点无需被更新。
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == 0x3f3f3f3f) return -1; //若无法到达某点，距离为无穷
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m --){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(c, g[a][b]); // 没有雍余数据
}
cout << dijkstra() << endl;
return 0;
}
可以用另个数组记录将点加入集合的顺序（即到达当前点的前一个点），可以递推出初始点走到某点的路径
Dijkstra + Heap
使用堆优化 dijkstra scan 步骤
复杂度：
- 时间：
- 空间：
- 稀疏图：
- 稠密图：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int e[N], ne[N], w[N], h[N], idx;
bool st[N];
int dist[N];
int n, m;
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; //大根堆，每次取出最小的距离
heap.push({0, 1});
while (heap.size()){
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
//若该点已经加入过集合，继续判断下一个，这里是为了跳过雍余的数据
st[ver] = true; //未加入过集合，加入集合
for (int i = h[ver] ; i != -1 ; i = ne[i]){
int j = e[i];
if (dist[j] > distance + w[i] ){
dist[j] = distance + w[i];
heap.push({dist[j], j}); //成功更新点后，全部加入堆中排序，待选取加入集合
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1; //若无法到达某点，距离为无穷
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c); // 会产生雍余数据
}
cout << dijkstra() << endl;
return 0;
}
Bellman-Ford
bellman_ford 只需要将每条边存下来，而不需要用复杂的数据结构存图，bellman_ford 算法适合用来解决有边数限制的最短路径问题。
实际含义：在 k 条边内找到起点到第 n 点(不一定是那个点)的最短距离
若限制为 k，即只能循环 k 次，每次循环将每条边进行一次松弛操作，松弛操作：由一条边的末端使用边的首端更新末端到起点的距离(如果能更新的话)
实际上的松弛操作会先更新与起点相连的所有边(由起点出发)，再更新与这些边相连的边，看起来就像是 bfs 一层一层向外扩展
其实挺形象的，每一次都只走一段，如果这段更新的距离比之前的距离短，就更新; 因为受次数限制，最后到达 n 点时并不一定是真正的最短距离
步骤：
- k 次循环
- 每一次循环更新所有的边
复杂度：
- 时间：
- 空间：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e4 + 10;
int dist[N], bk[N];
struct Edge{
int a, b, w;
}edge[M];
int n, m, k;
int bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0 ; i < k ; i ++){
memcpy(bk, dist, sizeof bk); //用上次的边更新，能防止某点已经被更新后，又拿去更新其他点，即能保证每次只走一条边
for (int j = 0 ; j < m ; j ++){
auto e = edge[j];
dist[e.b] = min(dist[e.b], bk[e.a] + e.w);
}
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 0 ; i < m ; i ++){
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edge[i] = {a, b, w};
}
bellman_ford();
if (dist[n] >= 0x3f3f3f3 / 2) puts("impossible"); //有负边权，更新时可能减掉了一部分
else cout << dist[n] << endl;
return 0;
}
Spfa
spfa 是 bellman-ford 的优化，在 bellman-ford 中每次循环都要更新 m 条边，事实上不需要每条边都更新。
若要到达 b 点，且途中经过 a 点，则要用 a 点来更新 b，当且仅当 a 点被更新过后，才需要更新 b 点(dist[b] = last[a] + g[a][b])
因此可以使用一个队列来保存更新过的点，仅当这些点被更新过，才拿他们去更新其他点，此时需要使用 st 数组记录更新过的点，防止重复冗余
（这里的 st 和 dijkstra，prim 中用于表示集合的 st 功能不同, 表示该点是否已经放入队列用于更新其他点，防止多余的更新）
含有负权边的最小路径问题，可以优先考虑 Spfa 算法，若只有正权边，且 spfa 过不了再考虑 dijkstra
步骤：
- pop（把队列中用于更新的边取出）
- updata（用更新过的边去更新其他边）
- add（把新更新的边加入队列待用于更新其他边）
复杂度：
- 时间：最优为，最坏为
- 空间：
- 稀疏图：
- 稠密图：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], h[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
void 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;
}
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
spfa();
if (dist[n] >= 0x3f3f3f3f / 2) puts("impossible");
else cout << dist[n];
return 0;
}
Floyd
floyd 基于 dp 想法，求两点间最短距离，若两点间存在其他点，则求该点到两端点的最小距离，若有多个点则可知道，只要使每个点间的距离最小，则两端点的距离是最小的。
🐷 记得 k 要在最外层，且初始化 dist[i][i] = 0，按理来说自环权重不应当全部默认为
0，也许和 dp 的信息有关, 待补充
路径：可以使用二维数组记录
path[i][j]，即每次更新距离都有path[i][j] = path[i][k], 那么就可以得到，i 到 j 的路径
复杂度：
- 时间：
- 空间：
#include <iostream>
using namespace std;
const int N = 2e4 + 10, INF = 1e9;
int d[N][N];
int n, m, q;
void floyd(){
for (int k = 1 ; k <= n ; k ++)
for (int i = 1 ; i <= n ; i ++)
for (int j = 1 ; j <= n ; j ++)
if (d[i][j] > d[i][k] + d[k][j])
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;
while (m --){
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}
floyd();
while (q --){
int a, b;
cin >> a >> b;
if (d[a][b] > INF / 2) puts("impossible");
else cout << d[a][b] << endl;
}
return 0;
}
spfa 判断负环
增加 cnt 数组，表示虚拟起点到某点经过的边数，如果cnt[x] >= n，即从虚拟起点到某点经过了 n 条边，那么起码经过了n+1个点，题意知总点数为n, 由抽屉原理可知其中经过了同一点(环)，又由于虚拟起点到所有点的初始化距离为0，那么起点到该点经过的环必然是负环(环的边总和为负数)，因为经过一次距离就会变小，如果不是负环，就不会经过了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int e[N], ne[N], w[N], h[N], idx;
int dist[N], cnt[N];
bool st[N];
int n, m;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa() {
queue<int> q;
for (int i = 1; i <= n; i ++) {
q.push(i);
st[i] = 1;
}
while(q.size()) {
auto t = q.front();
if (cnt[t] >= n) return true;
q.pop();
st[t] = 0;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > w[i] + dist[t]){
dist[j] = w[i] + dist[t];
if (!st[j]) q.push(j), cnt[j] = cnt[t] + 1;
}
}
}
return false;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa()) puts("Yes");
else puts("No");
return 0;
}
拓扑排序
拓扑序列是针对有向图的概念。
拓扑排序，是对一个有向无环图 G 进行拓扑排序，将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边(u,v)∈E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
可以证明有向无环图一定存在拓扑序列，因此有向无环图也被称为拓扑图
步骤：
- 在有向无环图中寻找所有入度为 0 的点（即没有其他点可以在该点前），入队
- 枚举这些点的出边，删掉这条边，假如队列中的点 A 连向 B，那么删除
A->B，B 的入度减一 - 若 B 的入度为零，则入队
判断：
当所有点都进入队列，则排序完成，队列中点的顺序就是拓扑序列，若队列中点数少于 n，则说明图有环，无拓扑序列。
可以知道如果图中存在环的话，没有一个点的入度为零，因此有环图无拓扑序列
有向无环图一定至少存在一个入度为零的点
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int q[N], d[N], hh = 0, tt = -1;
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topSort()
{
for (int i = 1 ; i <= n ; i ++)
{
if (!d[i]) q[++ tt] = i;
}
while (hh <= tt)
{
int t = q[hh ++];
for (int i = h[t] ; i != -1 ; i = ne[i])
{
int j = e[i];
d[j] --;
if (!d[j])
{
q[++ tt] = j;
}
}
}
if (tt == n - 1) return true;
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --)
{
int a, b;
cin >> a >> b;
d[b] ++;
add(a, b);
}
if (!topSort()) puts("-1");
else
{
for (int i = 0 ; i < n; i ++)
{
if (i) cout << ' ';
cout << q[i];
}
}
return 0;
}