图论 - 最短路(Dijkstra、Bellman-Ford、SPFA、Floyd)

文章目录

  • 前言
  • Part 1:朴素Dijkstra算法
    • 一、Dijkstra求最短路 I
      • 1.问题描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 输入样例:
        • 输出样例:
      • 2.算法
  • Part 2:堆优化Dijkstra算法
    • 一、Dijkstra求最短路 II
      • 1.题目描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 输入样例:
        • 输出样例:
      • 2.算法
  • Part 3:Bellman-Ford算法
    • 一、有边数限制的最短路
      • 1.题目描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 输入样例:
        • 输出样例:
      • 2.算法
  • Part 4:SPFA算法
    • 一、spfa求最短路
      • 1.题目描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 输入样例:
        • 输出样例:
      • 2.算法
    • 二、spfa判断负环
      • 1.题目描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 输入样例:
        • 输出样例:
      • 2.算法
  • Part 5:Floyd算法
    • 一、Floyd求最短路
      • 1.题目描述
        • 输入格式
        • 输出格式
        • 数据范围
        • 输入样例:
        • 输出样例:
      • 2.算法

前言

在这里插入图片描述

单源:在边权正数时,稠密图用朴素Dijkstra,稀疏图用堆优化Dijkstra;存在负权边时,一般用SPFA,但是如果限制在k步内,则用Bellman-Ford。多源:只有Floyd,这个由于时间复杂度太高,在算法比赛中很少遇见。

Part 1:朴素Dijkstra算法

一、Dijkstra求最短路 I

1.问题描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围

1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

2.算法

  • 即进行n(n为n的个数)次迭代去确定每个点到起点的最小值,最后输出的终点的即为我们要找的最短路的距离。
  • 每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离起点最短的点,且在已找到点集合中加上此点,更新其他未找到点距离起点的最短距离。
  • 稠密图用邻接矩阵存储
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N]; //存图
int dist[N]; //存距离起点距离
bool st[N]; //看是否已经计算过

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

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        //挑选最短距离点加入已选集合
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
                
		//用该点更新未选点距离起点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

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] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

Part 2:堆优化Dijkstra算法

一、Dijkstra求最短路 II

1.题目描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围

1≤n,m≤1.5×105,
图中涉及边长均不小于 0,且不超过 10000。
数据保证:如果最短路存在,则最短路的长度不超过 109

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

2.算法

  • 用小根堆优化找最小值的步骤
  • 稀疏图用邻接表存储
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010; // 把N改为150010就能ac

// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    // 有重边也不要紧,假设1->2有权重为2和3的边,再遍历到点1的时候2号点的距离会更新两次放入堆中
    // 这样堆中会有很多冗余的点,但是在弹出的时候还是会弹出最小值2+x(x为之前确定的最短路径),
    // 并标记st为true,所以下一次弹出3+x会continue不会向下执行。
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x]; 
    h[x] = idx++;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢,首先小根堆是根据距离来排的,所以有一个变量要是距离,
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点,不然怎么更新邻接点呢?所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒,pair排序时是先根据first,再根据second,
                         // 这里显然要根据距离排序
    while(heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;

        if(st[ver]) continue; //避免重复
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标,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];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

Part 3:Bellman-Ford算法

一、有边数限制的最短路

1.题目描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible

注意:图中可能 存在负权回路

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

点的编号为 1∼n。

输出格式

输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径,则输出 impossible

数据范围

1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n,
任意边长的绝对值不超过 10000。

输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3

2.算法

  • Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
  • 松弛模板:
for n次
   	for 所有边 a,b,w (松弛操作)
   		dist[b] = min(dist[b],back[a] + w)
  • 通俗的来讲就是:假设 1 号点到 n 号点是可达的,每一个点同时向指向的方向出发,更新相邻的点的最短距离,通过循环 n-1 次操作,若图中不存在负环,则 1 号点一定会到达 n 号点,若图中存在负环,则在 n-1 次松弛后一定还会更新
#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge 
{
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() 
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    //k次循环
    for (int i = 0; i < k; i++) 
    {
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) 
        {   
            //遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1; //可能更新后就不是0x3f3f3f3f,所以除以2
    else return dist[n];

}

int main() 
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) 
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");
    else cout << res;

    return 0;
}

Part 4:SPFA算法

一、spfa求最短路

1.题目描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

2.算法

  • SPFA算法仅仅只是对该算法的一个优化
  • Bellman_ford算法会遍历所有的边,但是有很多的边遍历了其实没有什么意义,我们只用遍历那些到源点距离变小的点所连接的边即可,只有当一个点的前驱结点更新了,该节点才会得到更新;因此考虑到这一点,我们将创建一个队列每一次加入距离被更新的结点
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010;
int h[N], e[N], w[N], ne[N], idx;//邻接表,存储图
int st[N];//标记顶点是不是在队列中
int dist[N];//保存最短路径的值
int q[N], hh, tt = -1;//队列


//图中添加边和边的端点
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa()
{
    q[++tt] = 1;//从1号顶点开始松弛,1号顶点入队
    dist[1] = 0;//1号到1号的距离为 0
    st[1] = 1;//1号顶点在队列中

	//不断进行松弛
    while(tt >= hh)
    {
        int a = q[hh++];//取对头记作a,进行松弛
        st[a] = 0;//取完队头后,a不在队列中了
        for(int i = h[a]; i != -1; i = ne[i])//遍历所有和a相连的点
        {
            int b = e[i], c = w[i];//获得和a相连的点和边
            
            //如果可以距离变得更短,则更新距离
            if(dist[b] > dist[a] + c)
            {

                dist[b] = dist[a] + c;//更新距离
				
				//如果没在队列中
                if(!st[b])
                {
                    q[++tt] = b;//入队
                    st[b] = 1;//打标记
                }
            }
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);//初始化邻接表
    memset(dist, 0x3f, sizeof dist);//初始化距离
    int n, m;//保存点的数量和边的数量
    cin >> n >> m;
    
    //读入每条边和边的端点
    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);//加入到邻接表
    }
    
    spfa();
    
    if(dist[n] == 0x3f3f3f3f )//如果到n点的距离是无穷,则不能到达 
        cout << "impossible";
    else cout << dist[n];//否则能到达,输出距离
    
    return 0;
}

二、spfa判断负环

1.题目描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

如果图中存在负权回路,则输出 Yes,否则输出 No

数据范围

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 -1
2 3 4
3 1 -4
输出样例:
Yes

2.算法

  • 需要从每个点都出发一次,才能完全确定此图中是否有环
  • cnt[j]=n 编号编号为j的节点是第n个加入路径的节点
  • 负环:环路之和为负, 求最短路的时候会不断在负环路打转
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], w[N], ne[N], idx;
int n, m;
queue<int> q;
int st[N], dist[N], cnt[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);
    for (int i = 1; i <= n; i++) 
    {
        q.push(i);
        st[i] = true;
    }
    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];
                cnt[j] = cnt[t] + 1;
                // 如果超过了n-1 
                // 根据抽屉原理,说明经过某个节点两次,则说明有环
                if (cnt[j] >= n) return true;
                if (!st[j]) 
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}

int main() 
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++) 
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if (spfa()) puts("Yes");
    else puts("No");
}

Part 5:Floyd算法

一、Floyd求最短路

1.题目描述

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出 impossible

数据范围

1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1

2.算法

  • 动态规划

  • 假设节点序号是从1到n。
    假设f[0][i][j]是一个n*n的矩阵,第i行第j列代表从i到j的权值,如果i到j有边,那么其值就为ci,j(边ij的权值)。
    如果没有边,那么其值就为无穷大。

    f[k][i][j]代表(k的取值范围是从1到n),在考虑了从1到k的节点作为中间经过的节点时,从i到j的最短路径的长度。

    比如,f[1][i][j]就代表了,在考虑了1节点作为中间经过的节点时,从i到j的最短路径的长度。
    分析可知,f[1][i][j]的值无非就是两种情况,而现在需要分析的路径也无非两种情况,i=>j,i=>1=>j:
    【1】f[0][i][j]:i=>j这种路径的长度,小于,i=>1=>j这种路径的长度
    【2】f[0][i][1]+f[0][1][j]:i=>1=>j这种路径的长度,小于,i=>j这种路径的长度
    形式化说明如下:
    f[k][i][j]可以从两种情况转移而来:
    【1】从f[k−1][i][j]转移而来,表示i到j的最短路径不经过k这个节点
    【2】从f[k−1][i][k]+f[k−1][k][j]转移而来,表示i到j的最短路径经过k这个节点

    总结就是:f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])
    从总结上来看,发现f[k]只可能与f[k−1]有关。

#include <cstring>
#include <iostream>
#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()
{
    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 a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/421968.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【学习笔记】Diffusion扩散模型

导读 Diffusion models是现在人工智能领域最火的方向之一&#xff0c;并引爆了AIGC领域&#xff0c;一大批创业公司随之诞生。 AIGC&#xff08;AI-Generated Content&#xff09;&#xff1a;人工智能创作内容的生产方式。 扩散模型Diffusion 扩散模型Duffison的训练过程 …

Redis【2】—— Redis特性 与 数据类型

Redis【2】—— Redis特性 与 数据类型 二、Redis 的基本介绍&#xff08;一&#xff09;关于 Redis1. 特性&#xff08;1&#xff09;在内存中存储数据&#xff08;2&#xff09;可编程&#xff08;3&#xff09;可扩展&#xff08;4&#xff09;持久化&#xff08;5&#xff…

场发射透射电子显微镜(FETEM)技术壁垒高 我国具备研制能力

场发射透射电子显微镜&#xff08;FETEM&#xff09;技术壁垒高 我国具备研制能力 场发射透射电子显微镜&#xff0c;简称场发射透射电镜&#xff0c;英文简称FETEM&#xff0c;产品主要由场发射电子枪、高压电源、照明透镜、偏转系统、物镜、投影镜、探测器、样品系统等组成。…

PlantUML简介

PlantUML简介 plantUML是一款开源的UML图绘制工具&#xff0c;支持通过文本来生成图形&#xff0c;使用起来非常高效。可以支持时序图、类图、对象图、活动图、思维导图等图形的绘制。你可以在IDEA中安装插件来使用PlantUML, 或者在Visual Studio Code中安装插件。 也可以在dra…

Nacos环境搭建 -- 服务注册与发现

为什么需要服务治理 在未引入服务治理模块之前&#xff0c;服务之间的通信是服务间直接发起并调用来实现的。只要知道了对应服务的服务名称、IP地址、端口号&#xff0c;就能够发起服务通信。比如A服务的IP地址为192.168.1.100:9000&#xff0c;B服务直接向该IP地址发起请求就…

超好看的下载页HTML源码分享

超好看的下载页HTML源码分享,源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面 下载地址&#xff1a;https://www.qqmu.com/2337.html

Java基于SpringBoot的网上租赁系统设计与实现论文

摘 要 本课题是根据用户的需要以及网络的优势建立的一个基于Spring Boot的网上租贸系统&#xff0c;来满足用户网络商品租赁的需求。 本网上租贸系统应用Java技术&#xff0c;MYSQL数据库存储数据&#xff0c;基于Spring Boot框架开发。在网站的整个开发过程中&#xff0c;首先…

NXP实战笔记(十一):32K3xx基于RTD-SDK在S32DS上配置LPSPI(同步、异步、DMA、主机、从机、中断、轮询)

目录 1、概述 2、RTD-SDK配置 2.1、配置目标 2.2、主、从机引脚配置 2.3、时钟配置 2.4、LPSPI配置 2.5、中断配置 2.6、DMA配置(使用DMA才会配置) 2、dma Logic Instance 2.7、RM配置(使用DMA的情况下必须配置此选项) 3、代码实现 1、概述 S32K3_低功耗LPSPI轮询…

Java基于微信小程序的房屋租赁、租房小程序,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

《TCP/IP详解 卷一》第12章 TCP初步介绍

目录 12.1 引言 12.1.1 ARQ和重传 12.1.2 滑动窗口 12.1.3 变量窗口&#xff1a;流量控制和拥塞控制 12.1.4 设置重传的超时值 12.2 TCP的引入 12.2.1 TCP服务模型 12.2.2 TCP可靠性 12.3 TCP头部和封装 12.4 总结 12.1 引言 关于TCP详细内容&#xff0c;原书有5个章…

【YOLO v5 v7 v8 小目标改进】新CNN架构 InceptionNeXt:怎么让大卷积核既好用又快

新CNN架构 InceptionNeXt&#xff1a;怎么让大卷积核既好用又快 提出背景问题: 如何提高大核心卷积的效率&#xff0c;同时保持或提升模型性能&#xff1f; 改进思路MetaNeXtInception深度卷积InceptionNeXt 小目标涨点YOLO v5 魔改YOLO v7 魔改YOLO v8 魔改 提出背景 论文&am…

【改进算法】【IHAOAVOA】天鹰优化算法和非洲秃鹫混合优化算法

目录 1 主要内容 IHAOAVOA流程图 主要创新点 2 部分代码 3 程序结果 4 下载链接 1 主要内容 该程序复现《IHAOAVOA: An improved hybrid aquila optimizer and African vultures optimization algorithm for global optimization problems》&#xff0c;天鹰优化算法&am…

【c++】理解vec.push_back(vector<int>())

vector<vector> vec; vec.push_back(vector()); vec.back().push_back(10); 定义一个二维向量&#xff08;动态数组&#xff09;: vector<vector> vec; 这行代码定义了一个名为vec的变量&#xff0c;它是一个向量&#xff08;动态数组&#xff09;&#xff0c;其中…

Apache Echarts介绍与入门

介绍 Apache ECharts 是一款基于 Javascript 的数据可视化图表库&#xff0c;提供直观&#xff0c;生动&#xff0c;可交互&#xff0c;可个性化定制的数据可视化图表。 官网地址&#xff1a;https://echarts.apache.org/zh/index.html 入门案例 Apache Echarts官方提供的快…

MySQL误truncate截断后数据恢复2024.3.1

近期很多MySQL数据丢失情况&#xff0c;很多是人为误操作导致。MySQL数据库丢失可能由truncate截断表、delete删除表中数据行、delete删除表、delete删除库、操作系统rm删除数据库文件、硬盘坏道等情况导致。本案例是一个误截断表导致的丢失。 不管哪种情况&#xff0c;第一时…

STM32USART串口数据包

文章目录 前言一、介绍部分数据包两种包装方式&#xff08;分割数据&#xff09;HEX数据包文本数据包 数据包的收发流程数据包的发送数据包的接收固定包长的hex数据包接收可变包长的文本数据包接收 二、实例部分固定包长的hex数据包接收连接线路代码实现 可变包长的文本数据包接…

JavaScript DOM操作笔记记录回忆总结

一、什么是DOM&#xff1f; 1、通过 HTML DOM&#xff0c;可访问 JavaScript HTML 文档的所有元素。 2、当网页被加载时&#xff0c;浏览器会创建页面的文档对象模型&#xff08;Document Object Model&#xff09; 二、操作DOM 1、在操作DOM之前&#xff0c;我们需要先获取到…

设计模式-结构型模式-外观模式

外观模式&#xff08;Facade&#xff09;&#xff0c;为子系统中的一组接口提供一个一致的界面&#xff0c;此模式定义了一个高层接口&#xff0c;这个接口使得这一子系统更加容易使用。[DP] 首先&#xff0c;定义子系统的各个组件接口和具体实现类&#xff1a; // 子系统组件接…

1美元持有ZKFair PFP-CyberArmy,潜在收益分析

3月2日&#xff0c;ZKFair PFP-CyberArmy 将在 Element 上正式开始Public Sale。

yolov9从头开始训练

yolov9从头开始训练 一、准备数据集 数据集相关文件存放布局如下 yolov9-datasets ├── train │ ├── images │ │ ├── image.jpg │ │ ├── │ └── labels │ ├── image.txt │ ├── ├── valid │ ├── images │ │ ├── image.jpg │ │ ├─…