【No.17】蓝桥杯图论上|最短路问题|Floyd算法|Dijkstra算法|蓝桥公园|蓝桥王国(C++)

图的基本概念

图:

  • 由点(node,或者 vertex)和连接点的边(edge)组成。
  • 图是点和边构成的网。
    树:
  • 特殊的图
  • 树,即连通无环图树的结点从根开始,层层扩展子树,是一种层次关系,这种层次关系,保证了树上不会出现环路。
  • 两点之间的路径:有且仅有一条路径。
  • 最近公共祖先。
图应用背景
  • 地图:路口、道路、过路费
  • 计算机网络:路由协议
  • 人际关系:六度空间理论
图的种类
  1. 无向无权图,边没有权值、没有方向;
  2. 有向无权图,边有方向、无权值;
  3. 加权无向图,边有权值,但没有方向;
  4. 加权有向图;
  5. 有向无环图(Directed Acyclic Graph,DAG)。
图算法的时间分析

图算法的复杂度和边的数量 E、点的数量 V 相关。
O(V+E):几乎是图问题中能达到的最好程度。
O(VlogE)、O(ElogV):很好的算法。
O(V2)、O(E2)或更高:不算是好的算法。

图的存储

能快速访问:图的存储,能让程序很快定位结点 u 和 v 的边(u, v) 。

  • 数组存边:简单、空间使用最少;无法快递定位
  • 邻接矩阵:简单、空间使用最大;定位最快 dis[a][b]
  • 邻接表:空间很少,定位较快
  • 链式前向星:空间更少,定位较快
    注: 存储方式跟题目相匹配,占用空间少定位快也不一定是问题的最优存储方式。
数组存边

优点:简单、最省空间。
缺点:无法定位某条边。
应用:bellman-ford 算法、最小生成树的 kruskal 算法

struct Edge
{
    int from, to, dis;  //from起始点,to终止点,dis权值
}e[M]; //结构体数组存边

cin >> n >> m;

for(int i = 1; i <= m; ++ i)
    cin >> e[i].from >> e[i].to >> e[i].dis;
邻接矩阵

二维数组: graph[NUM][NUM] 
无向图: graph[i][j] = graph[j][i] 
有向图: graph[i][j] != graph[j][i] 
权值: graph[i][j]存结点i到j的边的权值。 例如 graph[1][2]=3,graph[2][1]=5等等。 用 graph[i][j]=INF表示i,j之间无边。

优点:
  • 适合稠密图;
  • 编码非常简短;
  • 对边的存储、查询、更新等操作又快又简单。
缺点:
  • 存储复杂度 O(V^2)太高。V=10000 时,空间 100M。
  • 不能存储重边。
邻接表和链式前向星

邻接表(指针或数组下标)和链式前向星(容器模拟)的思路一样,只是表达方式不同。
应用场景:大稀疏图

优点:
  • 存储效率非常高,存储复杂度O(V+E)
  • 能存储重边
    图片描述
struct edge{
    int from, to; long long w; //起点,终点,权值。起点from并没有用到,e[i]的i就是from
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];          //用于存储图

最短路问题

最广为人知的图论问题就是最短路径问题。
简单图的最短路径

  • 树上的路径:任意 2 点之间只有一条路径
  • 所有边长都为 1 的图:用 BFS 搜最短路径,复杂度 O(n+m)
    普通图的最短路径
  • 边长:不一定等于 1,而且可能为负数
  • 算法:FloydDijkstraSPFA 等,各有应用场景,不可互相替代
最短路算法比较
问题边权算法时间复杂度
一个起点,一个终点非负数; 无边权(或边权为 1)Astar(K短路)/ 普通<O((m+n)logn)
双向广搜<O((m+n)logn)
贪心最优搜索<O(m+n)
一个起点到其他所有点无边权(或边权为 1)BFSO(m+n)
非负数Dijkstra(堆优化 优先队列)O((m+n)logn)
允许有负数SPFA<O(mn)
所有点对之间允许有负数Floyd-WarshallO(n^3)

什么算法也不能解决存在负环图的最短路的问题!最多是判断是否存在,或者找到负环。

网站推荐:CSAcademy Graph Editor
图片描述
方便图论的学习。

Floyd 算法

  • 最简单的最短路径算法,代码仅有 4 行
  • 存图:最简单的矩阵存图
  • 易懂,比暴力的搜索更简单易懂。
  • 效率不高,不能用于大图
  • 在某些场景下有自己的优势,难以替代。能做传递闭包问题(离散数学)
for(int k = 1; k <= n; k ++)         //floyd的三重循环
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)      // k循环在i、j循环外面
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

Floyd算法多源最短路算法,一次计算能得到图中每一对结点之间(多对多)的最短路径。 
DijkstraBellman-FordSPFA算法:单源最短路径算法(Single source shortest path algorithm),一次计算能得到一个起点到其他所有点(一对多)的最短路径。

Floyd 算法思想:动态规划

Floyd 算法的原理

  • 动态规划:求图上两点 ij 之间的最短距离,按“从小图到全图”的步骤,在逐步扩大图的过程中计算和更新最短路。
  • 定义状态:dp[k][i][j],i、j、k是点的编号,范围 1 ~ n。状态dp[k][i][j]表示在包含 1 ~ k 点的子图上,点对 i、j 之间的最短路。
  • 状态转移方程:从子图 1 ~ k-1 扩展到子图 1 ~ k
  • dp[k][i][j]= min(dp[k−1][i][j], dp[k−1][i][k]+dp[k−1][k][j])

首先是包含 1 ~ k-1 点的子图。 
dp[k−1][i][j]:不包含 k 点子图内的点对 i、j 的最短路;
dp[k−1][i][k]+dp[k−1][k][j]:经过 k 点的新路径的长度,即这条路径从 i 出发,先到 k,再从 k 到终点 j
比较:不经过 k 的最短路径dp[k−1][i][j]和经过 k 的新路径,较小者就是新的dp[k][i][j]

所以 Floyd 的原理就是每次引入一个新的点,用它去更新其他点的最短距离。

k 从 1 逐步扩展到 n:最后得到的dp[n][i][j]是点对 i、j 之间的最短路径长度。
初值dp[0][i][j]:若 i、j 是直连的,就是它们的边长;若不直连,赋值为无穷大。 
i、j 是任意点对:计算结束后得到了所有点对之间的最短路。

dp[k][i][j] = min(dp[k−1][i][j], dp[k−1][i][k]+dp[k−1][k][j]) 
用滚动数组简化:dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

for (int k = 1; k <= n; k ++)  //floyd的三重循环
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++)  //k循环在i、j循环的外面
			dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
			//比较:不经过k、经过k

特点:

  • 在一次计算后求得所有结点之间的最短距离。
  • 代码极其简单,是最简单的最短路算法。
  • 效率低下,计算复杂度是 O(n^3),只能用于 n < 300 的小规模的图。
  • 存图用邻接矩阵 dp[][] 。因为 Floyd 算法计算的结果是所有点对之间的最短路,本身就需要 n^2 的空间,用矩阵存储最合适。
  • 能判断负圈。
    • 负圈:若图中有权值为负的边,某个经过这个负边的环路,所有边长相加的总长度也是负数,这就是负圈。在这个负圈上每绕一圈,总长度就更小,从而陷入在负圈上兜圈子的死循环。
    • Floyd 算法很容易判断负圈,只要在算法运行过程出现任意一个 dp[i][i] < 0 就说明有负圈。因为 dp[i][i] 是从 i 出发,经过其他中转点绕一圈回到自己的最短路径,如果小于零,就存在负圈。
蓝桥公园

【题目描述】
小明来到了蓝桥公园。已知公园有N个景点,景点和景点之间一共有M条道路。小明有Q个观景计划,每个计划包含一个起点st和一个终点ed,表示他想从st去到ed。但是小明的体力有限,对于每个计划他想走最少的路完成,你可以帮帮他吗?
【输入描述】
输入第一行包含三个正整数N,M,Q。
第2到M+1行每行包含三个正整数u,v,w,表示 u、v之间存在一条距离为w的路。
第M+2到M+Q-1行每行包含两个正整类st,ed,其含义如题所述
1≤N≤400,1≤M≤NX(N-1)/2,Q≤10^3, 1≤u,v,st,ed≤n, 1≤w≤10^9
【输出描述】
输出共Q行,对应输入数据中的查询。若无法从st到达ed则输出-1。

#include <bits/stdc++.h>

using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL; 
//这样定义INF的好处是:INF <= INF+x 防止溢出
const int N= 405;
long long dp[N][N];
int n, m, q;

void input(){

}
void floyd()
{
	for(int k = 1; k <= n; k ++)
		for(int i = 1; i <= n; i ++)
			for(intj = 1; j <= n; j ++)
				dp[i][j]= min(dp[i][j], dp[i][k] + dp[k][j]);
}
int main()
{
	cin >> n>> m >> q;
	memset(dp, 0x3f, sizeof(dp));     //初始化
	for(int i = 1; i <= m; i ++)
	{
		int u, v;
		long long w;
		cin >> u >> V >> W;
		dp[u][v] = dp[v][u] = min(dp[u][v], w);   //防止有重边
	}
	floyd();
	while(q --)
	{
	int s, t;
	cin >> s >> t;
	if(dp[s][t] == INF)
		cout << "-1" << endl;
	else if(s == t)
		cout << "0" << endl;  //如果不这样,dp[il[i]不等于0
	else 
		cout << dp[s][t] << endl;
	return 0;
}

Dijkstra 算法

  • Dijkstra:单源最短路径问题。
  • 优点:非常高效而且稳定。
  • 缺点:只能处理不含有负权边的图。
  • 思路:贪心思想+优先队列。
算法思想

Dijkstra 算法算是贪心思想实现的,
首先把起点到所有点的距离存下来找个最短的,然后松弛一次再找出最短的,
所谓的松弛操作就是,遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近,如果更近了就更新距离,这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

为什么是每次都是找最小的?
因为最小边的不会被其它的点松弛,只有可能最小边去松弛别人。
如果存在一个点 K 能够松弛 ab 的话那么一定有 ak 距离加上 kb 的距离小于 ab,已知 ab 最短,所以不存在 ak+kb<ab。

Dijkstra 算法应用了贪心法的思想,即“抄近路走,肯定能找到最短路径”。

算法高效稳定:

  • Dijkstra 的每次迭代,只需要检查上次已经确定最短路径的那些结点的邻居,检查范围很小,算法是高效的;
  • 每次迭代,都能得到至少一个结点的最短路径,算法是稳定的

优先队列实现:

  • 每次往队列中放新数据时,按从小到大的顺序放,采用小顶堆的方式,复杂度是 O(logn),保证最小的数总在最前面;
  • 找最小值,直接取 B 的第一个数,复杂度是 O(1)。
  • 复杂度:用优先队列时,Dijkstra 算法的复杂度是 O(mlogn),是最高效的最短路算法。

维护两个集合:已确定最短路径的结点集合 A、这些结点向外扩散的邻居结点集合 B

  1. 把起点 s 放到 A 中,s-s的距离是0,相当于找到第一条最短路径,用这条最短路去松弛,把 s 所有的邻居放到 B 中。此时,邻居到 s 的距离就是直连距离。
  2. 从 B 中找出距离起点 s 最短的结点 u,放到 A 中。
  3. 把 u 所有的新邻居放到 B 中。显然,u 的每一条边都连接了一个邻居,每个新邻居都要加进去。其中 u 的一个新邻居 v,它到 s 的距离 dis(s, v) 等于 dis(s, u) + dis(u, v)。(要和原始距离dis(s, v)去比较)
  4. 重复(2)、(3),直到 B 为空时,结束。
    ![[Pasted image 20240325172845.png]]
A{1}; B{3, 10};
//会从3开始去扩展,因为3是最短的
A{1, 6}; B{3, 10, 4, 9};
//把6节点放进去,6到5是1,6到4是6,1到5是4,1到4是9
//把2节点放进去,6到2是2,1到2是5
A{1, 6}; B{3, 10, 4, 9, 5};
//排序后,从3开始,已经用6把所有松弛完了,所以3就没有了,从4开始
//到5这个点是4,所以把5加进来,用5这个点做松弛,5不能做松弛,因为到所有点都是正无穷
A{1, 6, 5}; B{10, 9, 5};
//用B里的5去松弛,从2开始,2到4是5,2到3是7,1到4是10,1到3是12
//之前的10被松弛了,1到6到2是5,1到2是10
//接下来用4这个点松弛,1到6到2到4到3是14,比12大,松弛不了
//下来用12去松弛...

Dijkstra 的局限性是边的权值不能为负数:
Dijkstra 基于 BFS,计算过程是从起点 s 逐步往外扩散的过程,每扩散一次就用贪心得到到一个点的最短路。
扩散要求路径越来越长,如果遇到一个负权边,会导致路径变短,使扩散失效。

蓝桥王国 lanqiaoOJ 题号 1122

题目描述
蓝桥王国一共有N 个建筑和M 条单向道路,每条道路都连接着两个建筑,每个建筑都有自己编号,分别为 1∼N。(其中皇宫的编号为 1)国王想让小明回答从皇宫到每个建筑的最短路径是多少,但紧张的小明此时已经无法思考,请你编写程序帮助小明回答国王的考核。
输入描述
输入第一行包含 2 个正整数 N,M。
第 2 到 M+1 行每行包含三个正整数 u,v,w,表示 u→v 之间存在一条距离为 w 的路。
1≤N≤3×105,1≤M≤106,1≤ui​,vi​≤N,0≤wi​≤10^9。
输出描述
输出仅一行,共 N 个数,分别表示从皇宫到编号为 1∼N 建筑的最短距离,两两之间用空格隔开。(如果无法到达则输出 −1)

解题思路:
本题为单源最短路的模板题,直接套模板即可,本题我们采用 Dijkstra。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
//这样定义INF的好处是: INF <= INF+x

const int N= 3e5+2;
struct edge{
    int from, to; long long w; //起点,终点,权值。起点from并没有用到,e[i]的i就是from
    edge(int a, int b,long long c){from=a; to=b; w=c;}
};
vector<edge>e[N];          //用于存储图
//定义一个排序准则
struct s_node{
    int id; long long n_dis;   //id:结点;n_dis:这个结点到起点的距离
    s_node(int b,long long c){id=b; n_dis=c;}
    bool operator < (const s_node & a) const
    { return n_dis > a.n_dis;}
};

int n,m;
int pre[N];                                //记录前驱结点,用于生成路径
void print_path(int s, int t) {            //打印从s到t的最短路
    if(s==t){ printf("%d ", s); return; }  //打印起点
    print_path(s, pre[t]);                 //先打印前一个点
    printf("%d ", t);                      //后打印当前点。最后打印的是终点t
}
long long  dis[N];         //记录所有结点到起点的距离
void dijkstra(){
    int s = 1;             //起点s是1
    bool done[N]; //done[i]=true表示到结点i的最短路径已经找到
    for (int i = 1; i <= n; i ++) 
    {
	    dis[i]=INF;   
	    done[i]=false; 
	}    //初始化,所有的距离都初始化为无穷大,都没找到
    dis[s]=0;                           //起点到自己的距离是0
    priority_queue <s_node> Q;          //优先队列,存结点信息
    Q.push(s_node(s, dis[s]));          //起点进队列,用它去松弛
    //当队列不为空的情况下
    while (!Q.empty())   {
        //每次在B中去一个最小值
        s_node u = Q.top();             //pop出距起点s距离最小的结点u
        Q.pop();            //取队头,用队头去松弛
        if(done[u.id])  continue;       //丢弃已经找到最短路径的结点。即集合A中的结点
        done[u.id]= true;//没有找到的话,就说明没有被用过,把它标记为使用
        //用它去松弛所有的点
        for (int i=0; i<e[u.id].size(); i++) {  //检查结点u的所有邻居
            edge y = e[u.id][i];         //u.id的第i个邻居是y.to
            if(done[y.to])  continue;    //丢弃已经找到最短路径的邻居结点
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                Q.push(s_node(y.to, dis[y.to]));  //扩展新的邻居,放到优先队列中
                //被松弛的点,再放到B的数列中来
                pre[y.to]=u.id;  //如果有需要,记录路径
            }
        }
    }
    // print_path(s,n);          //如果有需要,打印路径: 起点1,终点n
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)    e[i].clear();  //清空
    while (m--) {
        int u, v, w;  
        scanf("%d%d%lld", &u, &v, &w);
        e[u].push_back(edge(u, v, w));
        //以u为起点,vector里面放了uvw
     // e[v].push_back(edge(v, u, w));    
     //本题是单向道路,不需要建反边
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]>=INF)  cout<<"-1 ";
        else   printf("%lld ", dis[i]);
    }
}

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

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

相关文章

【C++】哈希应用之位图

&#x1f440;樊梓慕&#xff1a;个人主页 &#x1f3a5;个人专栏&#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》 &#x1f31d;每一个不曾起舞的日子&#xff0c;都是对生命的辜负 目录 前言 1.位图的概念 2.位…

一道很有意思的题目(考初始化)

这题很有意思&#xff0c;需要你对初始化够了解才能解出来 &#xff0c;现在我们来看一下吧。 这题通过分析得出考的是初始化。关于初始化有以下知识点 &#xff08;取自继承与多态&#xff08;继承部分&#xff09;这文章中&#xff09; 所以根据上方那段知识点可知&#xf…

【linux网络(一)】初识网络, 理解四层网络模型

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:Linux从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学更多操作系统知识   &#x1f51d;&#x1f51d; Linux网络 1. 前言2. 初识网络…

【Java程序设计】【C00361】基于Springboot的考勤管理系统(有论文)

基于Springboot的考勤管理系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 项目获取 &#x1f345;文末点击卡片获取源码&#x1f345; 开发环境 运行环境&#xff1a;推荐jdk1.8&#xff1b; 开发工具&#xff1a;eclipse以及idea&…

RWTH-PHOENIX Weather数据集模型说明和下载

RWTH-PHOENIX Weather 2014 T数据集说明: 德国公共电视台PHOENIX在三年内(2009 年至 2011 年) 录制了配有手语翻译的每日新闻和天气预报节目,并使用注释符号转录了 386 个版本的天气预报。 此外,我们使用自动语音识别和手动清理来转录原始德语语音。因此,该语料库允许训练…

电脑控制面板在哪?5招教你快速打开!

“我在执行一个任务时要进入电脑的控制面板中查看&#xff0c;但是我不知道电脑的控制面板在哪&#xff0c;谁能帮帮我呀&#xff1f;” 电脑控制面板是一个系统文件夹&#xff0c;它提供了各种对计算机系统进行设置和管理的工具。控制面板允许用户查看并操作基本的系统设置&am…

SAP ABAP-BOPF基础训练-01简介与架构

1. 介绍-Introduction ① BOPF是什么&#xff1f;BOPF(the Business Object Processing Framework)&#xff1a;业务对象处理框架 提供了一种增量和模块化的方法&#xff0c;以符合企业面向服务体系结构(eSOA)的方式实现业务对象&#xff1b; 部分平台基础层&#xff0c;软件组…

【笔记】深入理解JVM机制

&#x1f3a5; 个人主页&#xff1a;Dikz12&#x1f4d5;格言&#xff1a;吾愚多不敏&#xff0c;而愿加学欢迎大家&#x1f44d;点赞✍评论⭐收藏 目录 JVM 运⾏流程图 JVM 中内存区域划分 方法区 / 元数据区 堆 栈 程序计数器 本地方法栈 内存区域总结 JVM 中类加载过程 …

python网络爬虫实战教学——requests的使用(2)

文章目录 专栏导读1、POST请求2、响应3、Cookie设置 专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN 数据分析领域优质创作者&#xff0c;专注于分享python数据分析领域知识。 ✍ 本文录入于《python网络爬虫实战教学》&#xff0c;本专栏针对大学生、初级数据分析工程…

【c++】类和对象(二)this指针

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本节内容来到类和对象第二篇&#xff0c;本篇文章会带领大家了解this指针 目录 1.this指针1.1this指针的引出1.2this指针的特性1.3思考题1.4C语言和C实现Stack的对…

Qt|多线程串口通信

前篇:Qt|串口通信之同步数据收一包发一包数据 文章目录 创建工程添加串口通信类添加线程类主函数运行结果需求:串口下方的一些耗时操作并不想阻塞主进程的推进; 环境:windows10+VS2017+Qt5.14.2; 写在最前: 串口不支持跨线程操作,需要写信号槽形式传递;选择COM口下发指…

Allegro之轻松绕等长

如大家所见&#xff0c;这个世界通信的速率越来越快&#xff0c;生活的节奏也在飞驰&#xff0c;如果工作还是慢条斯理&#xff0c;你将是下一个淘汰的人。 高速PCB设计避免不了的要绕等长&#xff0c;然而有时候一个单板需要绕等长的总线很多&#xff0c;一个一个的绕下去&…

独立游戏《星尘异变》UE5 C++程序开发日志3——UEC++特供的数据类型

本篇日志将介绍FString&#xff0c;FText、FName的用法和相互转换&#xff0c;以及容器TMap&#xff0c;TArray的增删查改 一、字符串相关数据类型&#xff1a;FString、FText、FName FString是最接近std::string的类型&#xff0c;字符串本身可以看做一个存储char型的动态数…

数据容器-dict以及总结-Python

师从黑马程序员 字典的定义 同样使用{},不过存储的元素是以个个的&#xff1a;键值对&#xff0c;如下语法&#xff1a; #定义字典 my_dict1{"王力宏":99,"周杰伦":88,"林俊杰":77} #定义空字典 my_dict2{} my_dict3dict() print(f"字典1…

HarborCDN技术分析

一、介绍 简要介绍 ​​Harbor​​ 是由VMware公司开源的企业级的Docker Registry管理项目&#xff0c;它包括权限管理(RBAC)、LDAP、日志审核、管理界面、自我注册、镜像复制和中文支持等功能。Harbor 的所有组件都在 Dcoker 中部署&#xff0c;所以 Harbor 可使用 Docker C…

直击GDC 2024 (二):网易智企首次揭秘篮球游戏AI智能体!

近几日&#xff0c;世界级游戏开发者盛会 GDC&#xff08;Game Developers Conference&#xff09;2024 正在美国举行。全球游戏行业的精英都汇聚于旧金山&#xff0c;共同探索前沿的游戏开发技术、洞察行业最新趋势&#xff0c;并互相交流对未来发展的深刻见解。 &#xff08;…

校园跑腿小程序源码系统多校园版 跑腿达人入驻接单 带完整的安装代码包以及系统部署教程

在数字化时代的浪潮中&#xff0c;校园生活的便捷性和高效性成为了广大师生的共同追求。为了满足这一需求&#xff0c;罗峰给大家分享一款适用于多校园的跑腿小程序源码系统——校园跑腿小程序源码系统多校园版。该系统不仅提供了完整的安装代码包&#xff0c;还附带了详尽的系…

你以为的富贵包其实是脂肪瘤 整形外科医生为你科普脂肪瘤

脖子后面长的包都是富贵包吗&#xff1f;西安国际医学中心医院整形外科门诊主任冯登超曾接诊过一位七旬老人&#xff0c;他的颈部后方有一个直径约13厘米的巨大肿块&#xff0c;核磁共振检查提示右侧劲后皮下软组织内巨大囊性肿块。“他们以为是富贵包&#xff0c;实际上是脂肪…

C语言:给结构体取别名的4种方法

0 前言 在进行嵌入式开发的过程中&#xff0c;我们经常会见到typedef这个关键字&#xff0c;这个关键字的作用是给现有的类型取别名&#xff0c;在实际使用过程中往往是将一个复杂的类型名取一个简单的名字&#xff0c;便于我们的使用。就像我们给很熟的人取外号一样&#xff…

【大模型基础】什么是KV Cache?

哪里存在KV Cache&#xff1f; KV cache发生在多个token生成的步骤中&#xff0c;并且只发生在decoder中&#xff08;例如&#xff0c;decoder-only模型&#xff0c;如 GPT&#xff0c;或在encoder-decoder模型&#xff0c;如T5的decoder部分&#xff09;&#xff0c;BERT这样…