我的个人博客，welcome!

前言

本篇介绍算法竞赛中最最重点的一个部分搜索和图论。搜索分为广度优先搜索和深度优先搜索，在题目中非常的常见。而在图论中经常考察的最短路与最小生成树，是算法中极为重要一项基本功。

DFS(暴搜)

可以被称为“2022年度算法”的一款算法，实用价值极高！！！

DFS（深度优先搜索）本质上维护一个隐藏的stack，不具有最短性

空间：$O(h)$ （较节省空间）

DFS涉及两个重要的概念：

• 回溯：按代码理解就是需要return的地方
• 剪枝：提前判断一些肯定不满足条件的方法，并将其直接回溯

注意点：

• 回溯的过程中注意恢复现场
• 必然有一个标记访问的过程

全排列数字

将1-n之间的数字全排序

#include <iostream>
using namespace std;

const int N = 10;
int n;

int path[N];
bool st[N];

// u理解为树的层
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        puts("");
        return;
    }

    // 枚举1~n
    for (int i = 1; i <= n; i ++ ) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
}

int main() {
    scanf("%d", &n);

    dfs(0);

    return 0;
}

n-皇后

[HTML_REMOVED]

逐行搜

通过分析题目给出的规则，发现每一行只能出现一个皇后。加上列与对角线的限制，暴搜出所有满足题目的答案

dfs记录行数, 时间复杂度$O(n*n!)$

#include <iostream>
using namespace std;

const int N = 10;
int n;
char str[N][N];
// 分别记录列、对角线、反对角线
bool col[N], dg[N], udg[N];

// u为行数
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(str[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; i ++ ) {
        // y = x + b -> b = y - x
        // y = -x + b -> b = y + x
        if (!col[i] && !dg[i-u+n] && !udg[i+u]) {
            str[u][i] = 'Q';
            col[i] = true, dg[i-u+n] = true, udg[i+u] = true; //标记
            dfs(u+1);
            col[i] = false, dg[i-u+n] = false, udg[i+u] = false; //还原
            str[u][i] = '.';
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ )
            str[i][j] = '.';

    dfs(0);

    return 0;
}

逐格搜

dfs同时记录行数，列数，与皇后数， 时间复杂度$O(2^{n^2})$

每一格仅有两种情况即有皇后和无皇后

#include <iostream>
using namespace std;

const int N = 10;
int n;
char str[N][N];
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s) {
    // 走到一行的末尾，自动定位至下一行行头
    if (y == n) y = 0, x++;

    if (x == n) {
        if (s == n) {
            for (int i = 0; i < n; i ++ ) puts(str[i]);
            puts("");
        }
        return;
    }

    // 此格无皇后
    dfs(x, y + 1, s);

    // 此格有皇后
    if (!row[x] && !col[y] && !dg[y-x+n] && !udg[y+x]) {
        str[x][y] = 'Q';
        row[x] = true, col[y] = true, dg[y-x+n] = true, udg[y+x] = true;
        dfs(x, y + 1, s + 1);
        row[x] = false, col[y] = false, dg[y-x+n] = false, udg[y+x] = false;
        str[x][y] = '.';
    }

}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            str[i][j] = '.';

    dfs(0, 0, 0);

    return 0;
}

BFS

BFS（广度优先搜索）本质上维护一个queue，能够计算最短路

空间：$O(2^h)$ （所需要的空间和指数呈指数级别）

BFS记录路径

开辟一个数组，记录每一个点是由哪个点转移而来

但最后输出的结果为倒序

BFS之冲出迷宫

[HTML_REMOVED]

这道除了用到了BFS外，还有两处之前没有掌握的地方

1. 距离的记录：运用DP动态规划，记录下每一层点到起点的距离
2. 路径过程的记录：用一个数组记录当前点的前一个点

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N]; // 记录图
int d[N][N]; // 记录距离的同时标记此点是否已访问
PII q[N*N], path[N][N]; // 模拟队列，记录过程路径
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs() {
    int hh = 0, tt = -1;
    q[++tt] = {1, 1};

    memset(d, -1, sizeof d); // 初始化为-1
    d[1][1] = 0;

    while (hh <= tt) {
        auto t = q[hh++];

        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0 && d[x][y] == -1) {
                d[x][y] = d[t.x][t.y] + 1; // *DP记录下每一层的距离
                path[x][y] = t; // *记录下当前点的下一个点
                q[++tt] = {x, y};
            }
        }
    }

    return d[n][m];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    cout << dfs() << endl;

    // 反向遍历，得到起点到终点的路径
    int a = n, b = m;
    while (a >= 1 || b >= 1) {
        cout << a << ' ' << b << endl;
        auto t = path[a][b];
        a = t.first, b = t.second;
    }

    return 0;
}

树与图

树可以被看作一种特殊的图（只有一个根结点）

图的存储方式分别两种：

• 邻接矩阵：二维数组记录ab ba（无向图同时记录双向），无权重用0-1表示，有权重则记录对应的权重值

• 邻接表：如下

另，当题目中的数据超过$10^6$时，考虑用scanf, printf，以下则不限

邻接表存储

数组模拟邻接表

图中的每个结点都有一个单链表，用于存储该点可以到达的点

// h[]代表存储了多个结点，与单链表中的head比较记忆
int h[N], e[M], ne[M], idx;

memset(h, -1, sizeof h);

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

遍历

DFS

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);
    }
}

树的重心

难理解

[HTML_REMOVED]

首先这是比较绕的一道题，可能是我看了这么多算法以来，花了最多时间的一道

不过我大抵碰到了我的一个软肋，树+DFS。不容易理解的一个数据结构加上不易理解的一个算法，而恰恰这样题总是能够以很少的代码，解决很复杂的题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, M = 2*N;
int n;
bool st[N];
int h[N], e[M], ne[M], idx;
int ans = N;

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

// 返回以u为根结点子树的结点个数
int dfs(int u) {
    st[u] = true;

    // sum:存储 以u为根的树 的节点数，包括u
    // res:存储 删掉某个节点之后，最大的连通子图节点数
    int sum = 1, res = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            int s = dfs(j); // 返回以j为根结点的子树中的结点数，包括其本身
            res = max(res, s); // 比较u结点的每个子树大小，取最大
            sum += s; //计算u结点以下所有子树结点之和，包括u本身
        }
    }

    res = max(res, n - sum); // 最大的子树与u结点以上部分作比取最大值

    ans = min(ans, res); // 比较得出最大值中的最小值，即为重心

    return sum;
}

int main() {
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for(int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}

BFS

在权重为1的情况下，可以用BFS求解最短距离

queue<int> q;
int d[N]; // 存储距离

memset(h, -1, sizeof h);
int dfs() {
    q.push(1);

    memset(d, -1, sizeof d);
    d[1] = 0;

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

        for(int i = h[t]; i != -1; i = ne[i]) {
            if (d[i] == -1) {
                d[i] = d[t] + 1;
                q.push(i);
            }
        }
    }
    return d[n];
}

拓扑排序

[HTML_REMOVED]

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列

如上图，0->1->2->3->4即为拓扑序列。注意拓扑序列并不唯一

时间复杂度：$O(n+e)$，$n$ 表示点数，$e$ 表示边数

搜索入度为零的顶点所需的时间是$O(n)$，每个顶点入度减1的运算共执行了$e$次，由此得出时间复杂度

• 有向图才存在拓扑序列
• 利用BFS实现拓扑排序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N]; // d[]存储每个点的入度

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

// 核心代码
// 简言之，入度为0就入队，队列的次序即为拓扑序列
bool topsort() {
    int hh = 0, tt = -1;

    for(int i = 1; i <= n; i++)
        if (!d[i]) 
            q[++tt] = i; // 找到入度为0的突破口

    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] == 0) q[++tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列
    return tt == n-1;
}


int main() {
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b]++; // 入度+1
    }

    if (topsort()) {
        // 入队的顺序就是拓扑序
        for(int i = 0; i < n; i++) printf("%d ", q[i]);
        puts("");
    } else puts("-1");

    return 0;
}

最短路问题

单源最短路

从某一点到图上所有点的最短距离

朴素版Dijkstra

边权均为正，体现贪心

时间复杂度：$O(n^2+m)$，n个点m条边

适用于稠密图（$m$与$n^2$是一个数量级），使用邻接矩阵存储

int g[N][N]; // 邻接矩阵
int dist[N];
bool st[N]; // 标记是否已被访问过

memset(g, 0x3f, sizeof g);

int dijkstra() {
    // 初始化距离为正无穷！！
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    /* 有几个点就有几轮循环
     * 每轮选择距离最近的点，去更新其它点
     * 重复n次，就能使得每一个点都被选取到  */
    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; // 标记访问

        // 用这个距离最近的点，去更新其它的点距离原点的距离
        for(int j = 1; j <= n; j++) 
            dist[j] = min(dist[j], dist[t] + g[t][j]);

    }
    // 判断是否可以到达目标点
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

堆优化版Dijkstra

边权均为正

时间复杂度：$O(mlogn)$，n点m边

适用于稀疏图，数据结构邻接表

typedef pair<int, int> PII;

int h[N], e[N], ne[N], w[N], idx; // 带权重的邻接表
int dist[N];
bool st[N]; // 标记是否已被访问过

memset(h, -1, sizeof h);

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;
    else return dist[n];
}

Bellman-Ford算法

存在负边

时间复杂度：$O(nm)$

在求解最短路时，如果对所经过的边数有要求，可以使用此算法

在每一轮更新时，需对原始数组进行备份，防止出现此轮才更新的最短距离去更新其它点

int dist[N], backup[N];

struct {
    int a, b, w;
} edges[M];

bool 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); // 利用备份结果更新距离
        }
    }

    // 因处于负权图，所以不可直接与无穷判等
    if (dist[n] > 0x3f3f3f3f/2) return false; 
    return true;
}

SPFA算法

SPFA算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。

推荐使用！！！正权图也能过（被卡需换成堆优化Dijkstra）

时间复杂度：$O(m)$，最坏情况为$O(nm)$

可以简单理解为运用队列实现的宽搜来优化最短路

int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N]; // 标记该点是否在队列中，可先后重复进行队列

memset(h, -1, sizeof h);

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

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

    queue<int> q;
    q.push(1);
    st[1] = true; // 标记这点在队列内

    // 核心部分，类似一个BFS的过程
    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;
                }

            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return false;
    return true;
}

判负环

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

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

    for(int i = 1; i <= n; i++) {
        st[i] = true;
        q.push(i);
    }

    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;
                // n个点最多为n-1条边，超出判定为环
                if (cnt[j] >= n) return true;

                if (! st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

区别

Dijkstra是基于贪心的思想，每次选择最近的点去更新其它点，过后就不再访问。

而在SPFA算法中，只要有某个点的距离被更新了，就把它加到队列中，让它去更新与它相邻的其它点，所有每个点有被重复加入队列的可能

多源汇最短路

计算任意一点到任意一点的最短距离

Floyd算法

基于动态规划的思想

时间复杂度：$O(n^3)$

状态转移方法：$d[k][i][j] = d[k-1][i][k] + d[k-1][k][j]$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];

// Floyd算法核心
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() {
    scanf("%d%d%d", &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;
        scanf("%d%d%d", &a, &b, &c);

        d[a][b] = min(d[a][b], c); // 保留最小边
    }

    floyd();

    while(Q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > INF / 2) puts("impossible");
        else printf("%d\n", d[x][y]);
    }

    return 0;
}

最小生成树

[HTML_REMOVED]

Prim

首先选出权重最小的边ab加入集合，接着寻找与a和与b相关联的边，选取其中最小的加入集合。重复这一过程，从已知的点出发寻找最短边，同时要避免成环。最后形成最小生成树

朴素版Prim

联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

memset(g, 0x3f, sizeof g);

const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n, m;

int prim() {
    // 初始化所有距离为负无穷
    memset(dist, 0x3f, sizeof dist);

    int res = 0; // 用于记录权重
    // 循环迭代n次，在此写法中，默认选取了第一个点为起点
    for(int i = 0; i < n; i++) {
        int t = -1;
        // 在第一次循环中，默认选取了第一个点
        // 此后每次选取距离集合最近的点
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 && dist[j] > dist[t]))
                t = j;

        // 默认跳过第一次循环，从第二点开始即i=1开始计算
        if (i && dist[t] == INF) return INF; // 遍历结果若为负无穷，说明图不连通
        if (i) res += dist[t]; // 将本次最短距离记录到权重

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

        st[t] = true; // 标记访问，避免成环
    }

    return res;
}

Kruskal

依次选择出权重最小，次小，次次小……的边，使所有的点能够关联起来，同时避免成环，得到最小生成树

1. 将所有边按权重从小到大排序 $O(mlogm)$
2. 按顺序枚举每条边ab，权重c $O(m)$，如果ab此前在集合中还不连通，则将这条边加入到集合中（并查集）

int p[N];

struct Edge{
    int a, b, w;

    // 重载小于号，使得按权重从小到大排序
    bool operator< (const Edge& W) const {
        return w < W.w;
    }
} edges[N];

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

// 1. 按权重排序
sort(edges, edges + m);

// 初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;

int res = 0, cnt = 0;
// 2. 枚举每条边
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) { // 如果ab不连通
        res += w;
        cnt++;
        p[a] = b; // 使得ab连通，从而避免成环
    }
}

// 如果边数与顶点-1不相等，证明图无法连通
if (cnt < n - 1) puts("impossible");
else cout << res << endl;

二分图

二分图：将点均匀地分到两边，边在集合之间，集合内部没有边

一个图是二分图，当且仅当图中不含奇数环（环中边为奇数）

染色法

DFS，非常巧妙的一个算法，它的写法值得好好回味

$O(n+m)$

const int N = 1e5 + 10, M = 2*N;

memset(h, -1, sizeof h); // 当有多组数据时，每次都要初始化

int h[N], e[M], ne[M], idx; 
int color[N];

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; // c为1的时候，转换为2。反之为1
        } else if (color[j] == c) return false; // 如果染色重复(11,22)，则不是二分图
    }

    return true;
}

add(a, b), add(b, a); // 一般这种题为无向图

bool flag = false;
for(int i = 1; i <= n; i++) 
    if (!color[i]) {
        if (!dfs(i, 1)) {
            flag = true;
            break;
        }
    }

if (flag) puts("impossible");
else puts("Yes");

AcWing695.劣马

匈牙利算法

二分配对算法，“月老算法”。实现均匀分配，某一数有多个配对选项，而另一个数只有一个，为此进行合理分配，实现匹配的最大化，即完全匹配

$O(mn)$，实际运行时间远小于它

[HTML_REMOVED]

const int N = 510, M = 1e5 + 10;

memset(h, -1, sizeof h);

int h[N], e[M], ne[M], idx;
int match[N]; // match[右] = 左：记录右半部匹配的左半部是哪个点
bool st[N]; // 标记每轮的访问

bool find(int x) {
    // 枚举每个左半部的点，可以通到右半部的所有点
    for(int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];

        // 核心代码
        if (!st[j]) {
            st[j] = true;
            // 如果这个点此时还没有被匹配
            // 或者可以为其原先的匹配寻找下家
            if (match[j] == 0 || 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++;
}

参考资料

AcWing算法基础课