• 【AcWing 学习】图论与搜索

    图论与搜索

    搜索与图论

    1. 深度优先搜索 DFS
    2. 宽度优先搜索 BFS
    3. 树与图的存储
    4. 树与图的深度优先遍历
    5. 树与图的宽度优先遍历
    6. 拓扑排序

    深度优先搜索 DFS

    DFS 中重要的两个概念：回溯、剪枝

    BFS 一般和最短路径有关系，DFS 没有

    回溯注意点：记得恢复现场

    模板：

    void dfs (int k)
{
	if (到目的地)
	{
		输出解;
		return;
	}
	for (int i = 1; i <= 算法种数; i++)
	{
		if (满足条件)
		{
			保存结果，保存现场状态;
			dfs(k + 1);
			恢复保存结果之前的状态; // 回溯一步
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    排列数字

    题目：AcWing 842. 排列数字 - AcWing

    全排列的 DFS 过程：

    #include 
using namespace std;
const int N = 10;

int n;
int path[N]; // 路径
bool vis[N]; // 是否访问过

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i++) cout << path[i] << " ";
        puts("");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            // 标记已访问，并添加到路径
            path[u] = i;
            vis[i] = true;
            // 继续搜索
            dfs(u + 1);
            // 回溯
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0); // 从 path[0] 开始
    return 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

    N 皇后

    题目：AcWing 843. n-皇后问题 - AcWing

    参考题解：AcWing 843. n-皇后问题（按行枚举或按每个元素枚举） - AcWing

    解法1：按行枚举

    #include <iostream>
using namespace std;
const int N = 20;

int n;
char g[N][N]; // 存储路径
// bool 数组用来判断搜索的下一个位置是否可行
// col 列, dg 对角线(左上->右下), udg 反对角线(左下->右上)
bool col[N], dg[N], udg[N];

// 按行搜索
void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i++) puts(g[i]);
        puts("");
        return;
    }
    // 枚举 u 这一行，搜索合法的列
    int x = u;
    for (int y = 0; y < n; y++) 
    {
        // 剪枝(对于不满足要求的点，不再继续往下搜索)  
        if (!col[y] && !dg[y - x + n] && !udg[y + x]) 
        {
            // 标记已访问，并加入路径
            col[y] = dg[y - x + n] = udg[y + x] = true;
            g[u][y] = 'Q';
            // 向下搜索
            dfs(u + 1);
            // 回溯
            g[u][y] = '.';
            col[y] = dg[y - x + n] = udg[y + x] = false;  
        }
    }
}

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

    • 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

    解法2：按格子枚举

    #include 
using namespace std;
const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];

// 比较原始的 dfs 搜索，每一格都搜，s 表示皇后数量
void dfs(int x, int y, int s)
{
    // 换行
    if (y == n) y = 0, x++;
    if (x == n)
    {
        // 摆好了 n 个皇后
        if (s == n)
        {
            for (int i = 0; i < n; i++) puts(g[i]);
            puts("");
        }
        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); // 递归下一层
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

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

    • 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

    宽度优先搜索 BFS

    只有当所有边的权重都是 1 时，才可以用 BFS 求最短路。

    走迷宫

    题目：844. 走迷宫 - AcWing题库

    #include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII; // 二元对
// 方向向量
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 

int g[N][N], d[N][N];
int n, m; // n x m 的矩阵

void bfs()
{
	// 距离初始化为 —1
    memset(d, -1, sizeof d);
    d[0][0] = 0; // 起点初始化为 A
    
    queue<PII> q;
    q.push({0, 0});
    while (!q.empty())
    {
        PII p = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int x = p.first + dx[i], y = p.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[p.first][p.second] + 1;
                q.push({x, y});
            }
        }
    }
    cout << d[n - 1][m - 1] << endl;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    bfs();
    return 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

    输出路径：

    #include 
#include 
#include 
using namespace std;
const int N = 110;
typedef pair<int, int> PII;

int g[N][N], d[N][N]; // g 地图, d 距离
PII Prev[N][N]; // 记录前驱，用于输出路径
int n, m; // n x m 的矩阵

void bfs() 
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 方向向量

    queue<PII> q;
    q.push({0, 0});

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

    while (!q.empty())
    {
        PII p = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int x = p.first + dx[i], y = p.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[p.first][p.second] + 1; // 更新距离
                q.push({x, y}); // 新坐标入队
                Prev[x][y] = p; // 更新前驱
            }
        }
    }

    // 输出路径
    int x = n - 1, y = m - 1;
    while (x || y) {
        cout << x << " " << y << endl;
        // Prev[x][y] 存储的是能到达当前位置的位置
        PII p = Prev[x][y];
        x = p.first, y = p.second;
    }

    cout << d[n - 1][m - 1] << endl;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];
    bfs();
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    树和图的存储

    树是一种特殊的图（无环连通图）。

    无向图是特殊的有向图，主要学习有向图。

    有向图：（两个点之间有固定的方向）
a ---> b

无向图：（实际上就是每个方向都能走）
a ---> b
b ---> a

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    有向图的存储：

    • 邻接矩阵：二维数组，空间复杂度高（适合稠密图）
    • 邻接表：使用链表（适合稀疏图）

    规定：n - 图的点数，m - 图的边数

    图的邻接表存储：适用于稀疏图（ m 和 n 是一个量级）

    • 无权图
    int h[N]; // 链表头
int e[M]; // 节点的值
int ne[M]; // 下一个节点
int idx; // 当前节点的索引

// 插入一条 a 指向 b 的边
// 在 a 对应的单链表中插入一个节点 b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 有权图
    // 对于有权图，需要一个 w[] 存储权值
int h[N], e[M], ne[M], w[M], idx;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    图的邻接矩阵存储：适用于稠密图（m 和 n^2 一个量级）

    // g[i][j] = k 表示 i 指向 j 边长为 k
int g[N][N];

void add(int a, int b, int c)
{
	g[a][b] = min(g[a][b], c); // 处理重边，只需要记录最短的边
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    Bellman Ford 算法中使用的结构体进行存储边：

    // a 指向 b 权重为 w 的边
struct Edge {
	int a, b, w;
} edges[M];

    • 1
    • 2
    • 3
    • 4

    树和图的深度优先遍历

    DFS 模板：

    void dfs(int u) 
{
    st[u] = true; // 标记已访问

    int sum = 1, res = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    树的重心

    DFS 有个很好的特点，遍历的同时可以求出每个子树的大小。

    题目：846. 树的重心 - AcWing题库

    题解：AcWing 846. 树的重心 - AcWing

    #include 
#include 
#include 
using namespace std;
const int N = 100010, M = N * 2;

// 图的邻接表表示
int h[N]; // 链表头
int e[M]; // 节点的值
int ne[M]; // 下一个节点
int idx; // 当前节点的索引
bool st[N]; // 标记访问

int n;
int ans = N;

// 插入一条 a 指向 b 的边
// 在 a 对应的单链表中插入一个节点 b
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 - 当前子树点的数量, 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); // 当前子树的大小
            sum += s;
            res = max(res, s);
        };
    }
    // 树的重心：删除当前点后，剩余各个连通块中点数的最大值最小
    res = max(res, n - sum);
    ans = min(ans, res); 

    return sum;
}

int main() 
{
    // 初始化链表
    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    树和图的宽度优先遍历

    BFS 模板：

    queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

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

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点 j 已经被遍历过
            q.push(j);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    图中点的层次

    题目：847. 图中点的层次 - AcWing题库

    #include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int d[N]; // 存储每个节点距离起点的距离 d[1] = 0
int n, m; // n 个点 m 条边

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

int bfs()
{
    memset(d, -1, sizeof d);
    d[1] = 0;
    
    queue<int> q;
    q.push(1);
    
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        // 遍历 t 的每个邻边
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] == -1)
            {
                d[j] = d[t] + 1; // 存储 j 节点距离起点的举例，并标记已访问
                q.push(j);
            }
        }
    }
    return d[n];
}

int main()
{
    memset(h, -1, sizeof h);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl; 
    return 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
    • 53
    • 54
    • 55

    拓扑排序

    一个有向无环图，一定至少存在一个入度为 0 的点，一定存在拓扑序列。

    可利用反证法很快的得到结论，如果每个点都前驱节点，那么这个图将无穷无尽。

    入度与出度：

    入度为 0 表示没有任何一个点要求在前面，所有入度为 0 的点都可以排在前面位置。

    拓扑排序的思路：

    • 将入度为 0 的点入队，再删去该点指向的点的所有边
    • 若删去边后又有入度为 0 的点，再将这些点入队
    • 重复上述过程，直到队列为空
    • 最后队列中若入队过 n 个点，则可以实现拓扑序

    有向图的拓扑序列

    题目：848. 有向图的拓扑序列 - AcWing题库

    #include 
#include 
using namespace std;
const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int q[N], hh = 0, 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 topsort()
{
    // 将入度为 0 的点入队
    for (int i = 1; i <= n; i++)
        if (d[i] == 0) q[++tt] = i;
    // 不停的将入度为 0 的点指向的边删除，删除后入度为 0 则入队
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            d[j] --; // 删除 t->j 的边
            // 如果 j 的入度为 0 则入队
            if (d[j] == 0) q[++tt] = j;
        }
    }
    // n 个点的都入队则为拓扑图
    return tt == n - 1;
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b); // 加边 a -> b
        d[b]++; // 维护 b 入度
    }
    if (topsort())
    {
        for (int i = 0; i < n; i++) cout << q[i] << " ";
        puts("");
    } else puts("-1");
    return 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
    • 53
    • 54
    • 55

    最短路

    图论中的 源点 == 起点，汇点 == 终点

    规定：n - 图的点数，m - 图的边数
    最短路
    单源最短路
    所有边权都是正数
    朴素 Dijkstra 算法 O(n^2)
    堆优化版的 Dijkstra 算法 O(mlogn)
    存在负权边
    Bellman-Ford O(nm)
    SPFA 一般 O(m)，最坏 O(nm)
    多源最短路
    Floyd 算法 O(n^3)

    单源，只有一个起点的最短路。
    多源，多个不同起点到其他点的最短路。

    稠密图，指边数很多，m 和 n^2 是一个量级。
    稀疏图，指边数不多，m 和 n 是一个量级。

    Dijkstra

    朴素 Dijkstra

    Dijkstra 基于贪心，当有负权边时，局部最优不一定全局最优。

    题目：849. Dijkstra求最短路 I - AcWing题库

    整体思路：进行 n - 1 次迭代去确定每个点到起点的最小值。

    1. 初始化距离为无限大，源点到源点距离为 0
    2. 进行 n 次迭代：
      1. 找到当前没有确定最短路的点中，距离源点最近的点 t
      2. 使用 t 更新其他点的距离（比较 1–> j 和 1–>t–> j 的距离）

    时间复杂度分析：

    • 寻找路径最短的点： O ( n 2 ) O(n^2) O(n2)

    图解：AcWing 849. Dijkstra求最短路 I：图解 详细代码（图解） - AcWing

    使用邻接矩阵的写法：

    #include 
#include 
using namespace std;
const int N = 510;

int g[N][N]; // 邻接矩阵（稠密图）
int dist[N]; // 到源点的距离
bool st[N]; // 记录是否已经找到最短路
int n, m; // n 个点, m 条边

int dijkstra()
{
    // 距离初始化成无穷大
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; // 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 更新其他点距离
        // 遍历所有 t 可以达到的点 jd
        for (int j = 1; j <= n; j++)
            // 比较 1--> j 和 1--> t --> j 的距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) 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() << endl;
    return 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
    • 53
    • 54

    邻接表的写法：

    #include 
#include 
using namespace std;
const int N = 1e6 + 10;

int h[N], w[N], e[N], ne[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++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        // 找到未确定最短路的点中，距离源点最近的点 t
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = true;
        // 使用 t 更新邻点的最短路径
        for (int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j]; // 遍历 t 的邻点
            dist[k] = min(dist[k], dist[t] + w[j]);     
        }
    }
    if (dist[n] == 0x3f3f3f3f) 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() << endl;
}

    • 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
    堆优化的 Dijkstra

    题目：AcWing 850. Dijkstra求最短路 II - AcWing

    堆优化版的 Dijkstra 使用 最小堆 优化朴素版中的寻找距离最短的点。

    C++ 中的 pair 二元组默认支持比较，以 first 为第一关键字，second 为第二关键字，进行字典序比较。

    堆中存储的是一个 二元组 {距离, 节点编号}，从而优化 找出距离最短的点 这个过程。

    时间复杂度： O ( m l o g n ) O(mlogn) O(mlogn)，遍历所有点的出边，相当于遍历所有边，所以是 m 次

    邻接表：这题最合适的解法

    #include 
#include 
#include 
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII; // 堆里存储 { 距离, 节点编号 }

int h[N], w[N], e[N], ne[N], idx; // 邻接表（稀疏图）
int dist[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 ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 距离初始化为无穷大
    dist[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
    heap.push({0, 1}); // 1 号点距离源点距离为 1

    while (heap.size())
    {
        PII t = heap.top(); // 距离源点最近的点
        heap.pop();

        int ver = t.second; // 节点编号
        // int distance = t.first; // 源点距离 ver 的距离

        if (st[ver]) continue; // 如果距离已经确定，则跳过该点
        
        // 更新 ver 所指向的节点距离       
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
			// 比较 1-->j 和 1-->ver-->j 的距离
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j}); // 距离变小，则入堆
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) 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() << endl;
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    邻接矩阵：内存开辟过大，会报错

    #include 
#include 
#include 
#include 
using namespace std;
const int N = 5500;
typedef pair<int, int> PII; // {距离, 节点编号}

int g[N][N]; // 邻接矩阵
int dist[N], st[N];
int n, m;

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())
    {
        PII t = heap.top();
        heap.pop();
        
        int ver = t.second; // 距离源点最近的点
        if (st[ver]) continue;
        
        // 利用 t 更新它的邻点
        st[ver] = true; 
        for (int i = 1; i <= n; i++)
        {
            // 比较 1->i 和 1->ver->i
            if (dist[i] > dist[ver] + g[ver][i])
            {
                dist[i] = dist[ver] + g[ver][i];
                heap.push({dist[i], i});
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    else 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() << endl;
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    Bellman-Ford

    bellman-ford 算法擅长解决有边数限制的最短路问题。

    题目：853. 有边数限制的最短路 - AcWing题库

    此题边权可能为负数，所以不能使用 Dijkstra。
    参考：AcWing 853. 有边数限制的最短路 - AcWing
    Dijkstra 不能解决负权边是因为 Dijkstra 要求每个点被确定后 st[j] = true，dist[j] 就是最短距离了，之后就不能再被更新了（一锤子买卖），而如果有负权边的话，那已经确定的点的 dist[j] 不一定是最短了。

    思路：连续进行松弛，在每次松弛时把每条边更新一下，若在 n - 1 次松弛后还能更新，说明图中有负环，无法得出结果，否则完成。

    步骤：

    // back 数组是上一次迭代后 dist 数组的备份。
for n 次
	for 所有边 a,b,w (松弛操作)
		dist[b] = min(dist[b], back[a] + w)

    • 1
    • 2
    • 3
    • 4

    时间复杂度： O ( n m ) O(nm) O(nm)

    为什么需要 back 数组？

    参考：AcWing 853. 有边数限制的最短路 - AcWing

    • 为了避免如下的串联情况， 在边数限制为一条的情况下，节点 3 的距离应该是 3，但是由于串联情况，利用本轮更新的节点 2 更新了节点 3 的距离，所以现在节点 3 的距离是 2。

    • 正确做法是用上轮节点 2 更新的距离 – 无穷大，来更新节点 3， 再取最小值，所以节点 3 离起点的距离是 3。

    #include 
#include 
using namespace std;
const int N = 510, M = 10010;

int dist[N]; // 到源点的距离
int backup[N]; // 备份数组防止串联
int n, m, k;

// a 指向 b 权重为 w 的边
struct Edge {
    int a, b, w;
} edges[M];

void bellman_ford()
{
    // 初始化距离为无穷大
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; // 源点到源点距离为 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;
			// 比较 1->b 和 1->a->b 的路径长度
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n] << endl;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int a, b, w; 
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    bellman_ford();
    return 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

    SPFA

    SPFA 的限制很小，只要图中没有负环，就可以用。 SPFA 不仅可以处理负权图，也可以处理正权图。

    SPFA 可以看作对 Bellman_ford 的优化：

    • Bellman_ford 会遍历所有的边（固定 O ( n m ) O(nm) O(nm)），很多边的遍历没有意义，只用遍历那些到源点距离边小的点所连接的边即可。

    SPFA 和 Dijkstra 中的 st[] 数组：

    • Dijkstra 中的 st[] 中保存的是当前确定了到源点距离最短的点，确定以后不可逆。
    • SPFA 中的 st[] 仅仅表示当前发生过更新的点，是可逆的。

    SPFA 和 Dijksra 的思想：

    • Dijkstra 是基于贪心的思想，每次选择最近的点去更新其它点，过后就不再访问。
    • SPFA 中，只要有某个点的距离更新了，就加入到队列中，去更新其他点，所有每个点有可能重复入队。
    SPFA 求最短路

    题目：851. spfa求最短路 - AcWing题库

    参考：AcWing 851. s p f a 求最短路 − − − 图解 + 详细代码注释 \color{green}{spfa求最短路---图解 + 详细代码注释} spfa求最短路−−−图解+详细代码注释 - AcWing

    #include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;

int h[N], w[N], e[N], ne[N], idx; // 邻接表存储
int dist[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 号点的最短路距离
void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size())
    {
        int a = q.front();
        q.pop();
        st[a] = false;
        // 遍历 a 的出边指向的点
        for (int i = h[a]; i != -1; i = ne[i])
        {
            int b = e[i], c = w[i];
            if (dist[b] > dist[a] + c)
            {
                dist[b] = dist[a] + c;
                if (!st[b])
                {
                    q.push(b);
                    st[b] = true;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) puts("impossible");
    else cout << dist[n] << endl;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c);
    }
    spfa();
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    SPFA 判断负环

    题目：852. spfa判断负环 - AcWing题库

    求负环的常用方法，基于 SPFA，一般都用方法 2（该题也是用方法 2）：

    方法 1：统计每个点入队的次数，如果某个点入队 n 次，则说明存在负环
    方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于 n，则也说明存在环

    #include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;

int h[N], w[N], e[N], ne[N], idx; // 邻接表存储
int dist[N]; // 每个点距离源点的距离
int cnt[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 号点的最短路距离
bool spfa()
{
    queue<int> q;
    
    // 判断负环，只从一个点出发，有可能到达不了负环那里
    // 需要一开始就把所有结点放入队列，且标记进入了队列提高效率
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
        st[i] = true;
    }
    
    while (q.size())
    {
        int a = q.front();
        q.pop();
        st[a] = false;
        // 遍历 a 的出边指向的点
        for (int i = h[a]; i != -1; i = ne[i])
        {
            int b = e[i], c = w[i];
            if (dist[b] > dist[a] + c)
            {
                dist[b] = dist[a] + c;
                cnt[b] = cnt[a] + 1;
                if (cnt[b] >= n) return true;
                if (!st[b])
                {
                    q.push(b);
                    st[b] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c);
    }
    puts(spfa() ? "Yes" : "No");
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    Floyd

    Floyd 属于多源最短路径，能够求出任意 2 个顶点之间的最短路径，支持负权边（不能有负权回路）。

    时间复杂度： O ( n 3 ) O(n^3) O(n3)，效率比执行 n 次 Dijkstra 算法好。

    单源最短路径算法，对每个顶点求一次，同样可以求出任意 2 个顶点之间的最短路径。

    算法过程：

    1. 初始化 d[][] 数组，注意处理 自环 和 重边 的情况
    2. k, i, j 三重循环去更新 d[][] 数组

    原理：动态规划
    f [ k ] [ i ] [ j ] f[k][i][j] f[k][i][j] 代表（k 的取值范围是从 1 到 n），考虑从 1 到 k 的节点作为中间经过的节点时，从 i 到 j 的最短路径。
    状态转移方程： f [ k ] [ i ] [ j ] = m i n ( f [ k − 1 ] [ i ] [ j ] , f [ k − 1 ] [ i ] [ k ] + f [ k − 1 ] [ k ] [ j ] ) f[k][i][j] = min(f[k−1][i][j], f[k−1][i][k] + f[k−1][k][j]) f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])

    题目：AcWing 854. Floyd求最短路 - AcWing

    #include 
#include 
using namespace std;
const int N = 210, M = 20010, INF = 0x3f3f3f3f;

// d[i][j] 表示从 i 到 j 的最短路径
int d[N][N]; 
int n, m, k;

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 >> k;
    // 初始化
    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 (k --)
    {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > INF / 2) puts("impossible");
        else cout << d[a][b] << endl;
    }
    return 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

    最小生成树

    m - 边的数量，n - 点的数量
    稠密图：m 和 n^2 一个量级
    稀疏图：m 和 n 一个量级
    最小生成树
    普利姆算法(Prim)
    朴素版 Prim 算法 O(n^2)
    堆优化版 Prim 算法 O(mlogn)
    克鲁斯卡尔算法(Kruskal) O(mlogn)

    Kruskal 比 堆优化的 Prim 简单易用，所以堆优化的 Prim 并不常用。

    朴素 Prim

    给定一个无向图，在图中选择若干条边把图的所有节点连起来，要求边长之和最小，就是最小生成树。

    整体思路：

    1. 初始化距离为无限大
    2. 进行 n 次迭代：
      1. 找到一个还没有连通起来，但是距离连通部分最近的点 t
      2. 使用 t 更新其他点到连通部分的距离

    dijkstra 是使用 t 更新其他点到 源点 的距离

    题目：858. Prim算法求最小生成树 - AcWing题库

    题解：AcWing 858. Prim算法求最小生成树：图解+详细代码注释（带上了保存路径） - AcWing

    #include 
#include 
using namespace std;
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);
    dist[1] = 0; // 从 1 号点开始生成
    
    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 (dist[t] == INF) return INF;
        res += dist[t]; // 先更新最小生成树的边权和，防止有自环
        // 更新生成树外的点到生成树的距离
        for (int j = 1; j <= n; j++) 
            // t->j 距离小于原来的距离，则更新
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true; // 标记该点已经在生成树中
    }
    return res;
}

int main()
{
    // 各个点之间的距离初始化成无穷
    memset(g, 0x3f, sizeof g);
    
    cin >> n >> m;
    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c); // 无向图，有重边
    }
    
    int t = prim(); // 求最小生成树

    if (t == INF) puts("impossible");
    else cout << t << endl;
    
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57

    堆优化的 Prim

    此部分略过，原因如下：

    • 堆优化的 Prim 与 堆优化的 Dijkstra 思路完全一样。
    • 对于最小生成树来说，Kruskal 算法更加简单高效。

    Kruskal

    视频讲解：最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩_bilibili

    Kruskal 算法：

    1. 将所有边按权重从小到大排序 O(mlogm)
    2. 从小到大枚举每条边 a -> b。
      • 如果这个边和之前的边不会组成回路，就选择这条边 ，反之舍去。
      • 直到具有 n 个顶点的连通网筛选出 n - 1 条边为止。
      • 筛选出来的边和所有的顶点构成此连通网的最小生成树。

    判断是否会产生回路的方法为：使用并查集。

    • 初始状态下各个顶点在不同的集合中。
    • 遍历过程的每条边，判断这两个顶点的是否在一个集合中。
    • 如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。

    题目：859. Kruskal算法求最小生成树 - AcWing题库

    图解：AcWing 859. 思路详解 + 代码注释 + 图解 \color{green}{思路详解+代码注释+图解} 思路详解+代码注释+图解 - AcWing

    #include 
#include 
#include 
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int p[N]; // 并查集
int n, m;

struct Edge {
    int a, b, w;
    // 重载 < 符号，方便调用排序函数
    bool operator < (const Edge &W) const
    {
        return w < W.w;
    }
} edges[N]; 

// 并查集，找祖宗节点
int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    int cnt = 0; // 全部加入到树的集合中边的数量(可能有多个集合)
    int res = 0; // 最小生成树的边权重之和
    
    // 按边权从小到大顺序遍历所有边
    for (int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb) // a b 不在一个集合中
        {
            p[pa] = p[pb]; // 合并 a b 
            res += w; // 计算边权和     
            cnt ++; // 全部集合中的边数量 + 1
        }
    }
    
    // 树中有 n 个节点便有 n-1 条边，如果 cnt 不等于 n-1，说明无法生成有 n 个节点的树
    if (cnt < n - 1) return INF; // 无法生成最小生成树
    return res;
}

int main()
{
    cin >> n >> m; 
    // 初始化并查集
    for (int i = 0; i < n; i++) p[i] = i;
    // 建图
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    // 按照边权升序排序
    sort(edges, edges + m);
    
    int t = kruskal();
    if (t == INF) puts("impossible");
    else cout << t;
    
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    二分图
    二分图
    染色法 O(n + m)
    匈牙利算法，最差 O(mn)，实际一般远小于 O(mn)

    二分图，当且仅当图中不含奇数环。由于图中不含奇数环，所以染色过程中一定没有矛盾。

    二分图：一定不含有奇数环，可能包含长度为偶数的环， 不一定是连通图

    通俗易懂的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。

    下图是个二分图：

    下图不是二分图：

    染色法

    DFS 代码思路：

    • 颜色 1 和 2 表示不同颜色，0 表示 未染色
    • 遍历所有点，每次将未染色的点进行 DFS（默认染成 1 或者 2）
      • 如果其邻边未染色，则对其邻边进行 DFS 染色
      • 如果其邻边已经染色，判断颜色是否是 3 - c

    由于某个点染色成功不代表整个图就是二分图，因此只有某个点染色失败才能立刻 break / return
    - 染色失败相当于存在相邻的 2 个点染了相同的颜色

    题目：860. 染色法判定二分图 - AcWing题库

    #include 
#include 
using namespace std;
// 由于是无向图，顶点数最大是 N，那么边数最大是顶点数的 2 倍
const int N = 1e5 + 10, M = N + N;

int h[N], e[M], ne[M], idx;
// 记录节点被染成哪种颜色, 0 表示未染色, 1, 2 是两种不同的颜色
int color[N];
int n, m;

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

// 深度优先遍历对 u 及其邻点进行染色，并返回是否能够完成染色操作
bool dfs(int u, int c)
{
    color[u] = c; // 对 u 染色
    // 遍历 u 所有邻点并染色
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        // 邻点没有颜色，则递归处理这个邻点(1 染成 2，2 染成 1)
        if (!color[j] && !dfs(j, 3 - c))
            return false;
        // 已经染色，且颜色不是 3 - c，则冲突
        else if (color[j] && color[j] != 3 - c)
            return false;   
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    // 读入边
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); // 无向图
    }
    
    for (int i = 1; i <= n; i++) // 遍历所有点
        if (!color[i]) // 没有染色
        {
            if (!dfs(i, 1)) // 染色该点，并递归处理和它相邻的点
            {
                puts("No");
                return 0;
            }
        }
    puts("Yes");
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    BFS 代码思路：

    • 颜色 1 和 2 表示不同颜色，0 表示 未染色
    • 定义 queue 存 PII，表示 <点编号, 颜色>
    • 遍历所有点，将未染色的点都进行 BFS
    • 队列初始化将第 i 个点入队（默认颜色可以是 1 或 2）
      • while (队列不空)
      • 每次获取队头 t，并遍历队头 t 的所有邻边
        • 若邻边的点未染色，则染上与队头 t 相反的颜色，并添加到队列
        • 若邻边的点已经染色且与队头 t 的颜色相同, 则返回 false
    #include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;

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

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

// 对 u 进行染色，并对其邻边进行染色
bool bfs(int u)
{
    queue<int> q;
    q.push(u);
    color[u] = 1;

    while (q.size())
    {
        int t = q.front();
        q.pop();
        int c = color[t]; // 颜色

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            // 未染色
            if (!color[j])
            {
                color[j] = 3 - c;
                q.push(j);
            }
            // 已染色且与 t 颜色相同
            else if (color[j] && color[j] == c)
                return false;
        }
    }

    return true;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (!bfs(i))
            {
                flag = false;
                break;
            }
        }
    }
    puts(flag ? "Yes" : "No");

    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    匈牙利算法

    有趣的示例： 匈牙利算法（简单易懂）_一只大秀逗的博客-CSDN博客

    题目：861. 二分图的最大匹配 - AcWing题库

    题解：AcWing 861. 二分图的最大匹配 - AcWing

    #include 
#include 
using namespace std;
const int N = 510, M = 1e5 + 10;

int h[N], e[M], ne[M], idx;
// st[j] = a 表示一轮模拟匹配中，女孩 j 被男孩 a 预定了
bool st[N];
// match[j] = a 表示女孩 j 现有配对男友是 a
int match[N];
// n1 n2 分别是两个点集的个数
int n1, n2, m;

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

// 如果 x 参与模拟配对，会不会使匹配数增多
bool find(int x)
{
    // 遍历 x 喜欢的女孩
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i]; // x 喜欢的女孩 j
        if (!st[j]) // 如果这轮匹配中，女孩 j 未被预定
        {
            st[j] = true; // x 预定女孩 j
            // 如果女孩 j 没有男朋友，或她原来的男朋友能够预定其他喜欢的女孩，则配对成功
            if (!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    // 自己喜欢的女孩全部被预定了，配对失败
    return false; 
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n1 >> n2 >> m;
    while (m--)
    {
        int a, b;
        cin >> 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 << endl;
    return 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
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
  • 相关阅读:
    北大肖臻老师《区块链技术与应用》系列课程学习笔记[22]以太坊-智能合约-2
    香港回归20余年，图扑数字孪生港珠澳大桥，超震撼
    Bazzite：专为 Steam Deck 和 PC 上的 Linux 游戏打造的发行版
    【数据库编程-SQLite3（四）】基本常用操作
    初识设计模式 - 单例模式
    Python模拟试卷2023(1)
    K8S 安全机制
    机器学习、深度学习、强化学习、迁移学习的关联与区别
    java-net-php-python-springboot企业员工管理系统演示录像计算机毕业设计程序
    美国开源数据库ScyllaDB完成4300万美元融资
  • 原文地址：https://blog.csdn.net/weixin_43734095/article/details/126414566