今日学习为图论小进阶最小生成树和最短路两个“最”字表明这两种算法都和贪心有关不会贪心出门进我主页~~~下面我们就具体来看看这两种算法吧1.最小生成树要想了解最小生成树应如何计算首先我们要了解如何做到生成树生成树对一个具有 n 个点的连通图进行遍历对于遍历后的子图其包含原图中所有的点且保持图连通最后 的结构一定是一个具有 n-1 条边的树通常称为生成树。如图右方的两个图即为生成树了解生成树下面我们在了解一下最小生成树的操作原理对于一个无向联通图的最小生成树就是在保证所有点全部联通的情况下让每条边的边权总和尽可能的小 这就是最小生成树。等我们再次了解了最小生成树现在就上算法吧最经典的算法就是克鲁斯卡尔Kruskal算法和普利姆算法Prim这两种算法都基于贪心的思想一种是基于边权的贪心另一种则是点的贪心。克鲁斯卡尔Kruskal算法该算法初始将图视为森林图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性不构成环 的树之间建立连边。通俗来讲,我们在保证从每个点出发都能到达任意一个点的情况下将这个完全图的边权从小到大排序如下图将边权从小到大排序后 我们可以依据点的遍历情况依次在最小生成树中加边为防止在生成树中建立无效的边权从而导致最小生成树的生成我们可以判断枚举每一条边中的两个端点是否在统一集合中如果是则该边建立无效跳过反之则将边加入同时将两点并入集合中此处我们可以采用并查集的思想来做并查集的具体内容此处不在讲解~~生成后的最小生成树如下kruskal算法的具体代码如下展示#includebits/stdc.h #define ll long long #define db double #define endl \n using namespace std; const int N1e510; int f[N],vis[N],ans,n,m; struct wy{int x,y,v;}b[N]; //并查集找父亲路径压缩. inline int getf(int x) {return f[x]x?x:f[x]getf(f[x]);} //kruskal算法 inline void kruskal() { for(int i1;in;i) f[i]i; int cnt0;//记录已经是最小生成树的边 for(int i1;im;i) { //找出当前两个端点的所属的集合 int txgetf(b[i].x),tygetf(b[i].y),vb[i].v; if(tx!ty) //所属集合不同说明当前边作为最小生成树的边 { f[tx]ty; //两个集合合并 vis[i]1; //标记当前边为最小生成树边 ansv; //记录最小生成树权值和. if(cntn-1) return;//如果当前边已经达到n-1说明最小生成树已经生成无需继续查找其他边. } } }克鲁斯卡尔在解决最小生成树中应用最为广泛一定要会普里姆PRIM算法前文中提到克鲁斯卡尔算法是基于边权值的贪心而PRIM算法则是基于点的贪心在找最小生成树时将顶点分为两类一类是在查找的过程中已经包含在生成树中的顶点 假设为 A 类剩下的为另一类假设为 B 类。对于给定的连通网起始状态全部顶点都归为 B 类。在找最小生成树时选定任意一个顶点作为起始 点并将之从 B 类移至 A 类然后找出 B 类中到 A 类中的顶点之间权值最小的顶点将之从 B 类移至 A 类如此重复直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。具体实现过程我们可以用一个小根堆或是使用大根堆但将边权取负入队存入需要拓展的节点和 其边权每次取出代价最小的节点看是否在最小生成树中若不在则将其加入并且将其邻接点全部入队。当加入的点数n时返回输出答案。具体代码如下void prim(){ priority_queuekk q; q.push({0,1}); while(q.size()){ kk opq.top(); int vop.d,xxop.id; q.pop(); if(vis[xx]) continue; maxxv; cnt; vis[xx]1; if(cntn) return; for(auto i:a[xx]){ int yyi.first,vvi.second; if(!vis[yy]){ q.push({vv,yy}); } } } }下面关于最小生成树我们再来看一道例题题目描述Farmer John希望把水源引入他的N (1N3001N300) 个牧场,牧场的编号是1 ~ N.他将水源引入某个牧场的方法有两个,一个是在牧场中打一口井,另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连.在牧场i中打井的费用是Wi (1Wi100000).把牧场i和j用一根管道相连的费用是Pij (1Pij100000,PijPji, Pii0).请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源.输入格式第11行: 一个正整数N.第2 ~N1行: 第i1行包含一个正整数Wi.第N2~2N1行: 第N1i行包含N个用空格分隔的正整数,第j个数表示Pij.输出格式总共有四个牧场.在11号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要33的费用.在不同的牧场间建立管道需要2,3或4的费用.input4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0Copyoutput9本题中给出了一个邻接矩阵表示Pij修管道的费用其实也就是给出了每两点之间的一条边和其边权很容易让人想到最小生成树但本题的难点在于有一个修井的费用可以代替修管道的费用呢那该如何处理呢我们考虑假设在n号点外面有一口井n1,而修井的费用其实就是与这口大井连边问题就转化好了求n1个点的最小生成树具体核心代码如下for(int i1;in;i){ scanf(%d,a[i]); edge[bs].ui,edge[bs].vn1,edge[bs].ca[i]; } for(int i1;in;i){ for(int j1;jn;j){ int x; scanf(%d,x); if(ji) edge[bs].ui,edge[bs].vj,edge[bs].cx; } }void kruskal(){ for(int i1;in;i) f[i]i; for(int i1;ibs;i){ int xxget(edge[i].u),yyget(edge[i].v); if(xx!yy){ f[xx]yy; ansedge[i].c; if(cntn) return; } } }最短路给定一个有权图最短路径就是从一点出发到达另一点的权值之和最小的路径。最短路径的分类最短路径问题分为单源最短路径问题和多源最短路径问题单源最短路径求解的是从图中的一个顶点出发到达图中所有顶点的最短路径算法有Dijkstra算法迪杰斯特拉算法、Spfa算法。多源最短路径求解的是同一个图中任意两个顶点之间的最短路径。算法有Floyd-Warshall算法弗洛伊德算法Dijkstra算法Dijkstra算法是一种用于在加权图中寻找单源最短路径的算法。它适用于边权非负的图通过逐步扩展最短路径树来找到从源点到所有其他顶点的最短路径。算法核心思想算法维护一个集合S包含已确定最短路径的顶点以及一个优先队列或最小堆用于选择当前距离源点最近的未访问顶点。每次从优先队列中取出距离最小的顶点松弛其邻居的距离。注意事项时间复杂度为O((VE)logV)其中V是顶点数E是边数。仅适用于非负权重的图负权边需使用Bellman-Ford算法。优先队列的实现需使用小顶堆C中priority_queue默认是大顶堆需通过greater调整或者在存入时存进负边权。SPFA算法就是容易死了感兴趣的同学如果想知道它为什么死了可以详见NOI2018day1 t1归程~~~SPFA算法是我们的国产算法那让我们代入当事人的视角来详细分析一下SPFA算法在SPFA算法诞生之前应用于单源最短路径的算法只有Dijkstra算法虽然Dijkstra算法的时间复杂度很优秀但其缺点也有很多例如无法处理负边权负环等问题这使得当时算法的局限性很多但这时SPFA算法应运而生。SPFA算法基于Dijkstra算法的基础上让每个点在对点与点之间进行松弛操作后将vis数组重新标记为0保证每个点可以不断地在更新后进行松弛操作。通俗来讲再无负数的情况下3n一定严格大于2但一旦有了负数3n与2的大小关系就无法保证这时我们就需要分类讨论而 SPFA算法就是在Dijkstra算法上进行了k次分类讨论。因为有了分类讨论SPFA算法在实用性上要比Dijkstra算法要强出不少在解决负环问题上SPFA算法可以记录节点入队次数若超过|V|次则存在负权环”在解决最长路问题上SPFA可以让每个点都对其进行最长路的松弛操作从而完成对最长路的处理。它唯一其最致命的缺点就是时间复杂度不稳定为Okm),k的数值要根据图的具体形状来判断最坏的情况下SPFA的时间复杂度为Onm),当n的数值1e4时SPFA会超时限免咱们来看一道经典例题题目描述C 国有 n 个大城市和 m 条道路每条道路连接这 nn 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 mm 条道路中有一部分为单向通行的道路一部分为双向通行的道路双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔各地的资源分布情况各不相同这就导致了同一种商品在不同城市的价格不一定相同。但是同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后便决定在旅游的同时利用商品在不同城市中的差价赚回一点旅费。设 C 国 nn 个城市的标号从 1∼n阿龙决定从 1 号城市出发并最终在 n 号城市结束自己的旅行。在旅游的过程中任何城市可以重复经过多次但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费他会选择一个经过的城市买入他最喜欢的商品——水晶球并在之后经过的另一个城市卖出这个水晶球用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游他决定这个贸易只进行最多一次当然在赚不到差价的情况下他就无需进行贸易。假设 C 国有 5 个大城市城市的编号和道路连接情况如下图单向箭头表示这条道路为单向通行双向箭头表示这条道路为双向通行。假设 11 ~ nn 号城市的水晶球价格分别为 4,3,5,6,14,3,5,6,1 。阿龙可以选择如下一条线路1→2→3→5并在 22 号城市以 33 的价格买入水晶球在 33 号城市以 55 的价格卖出水晶球赚取的旅费数为 22 。阿龙也可以选择如下一条线路 1→4→5→4→5并在第 11 次到达 55 号城市时以 11 的价格买入水晶球在第 2 次到达 4 号城市时以 66 的价格卖出水晶球赚取的旅费数为 55 。现在给出 nn个城市的水晶球价格 mm 条道路的信息每条道路所连接的两个城市的编号以及该条道路的通行情况。请你告诉阿龙他最多能赚取多少旅费。输入格式输入第一行包含 2 个正整数 nn 和 mm中间用一个空格隔开分别表示城市的数目和道路的数目。第二行 nn 个正整数每两个整数之间用一个空格隔开按标号顺序分别表示这 nn 个城市的商品价格。接下来 mm 行每行有 33 个正整数 x,y,z每两个整数之间用一个空格隔开。如果 z1表示这条道路是城市 x 到城市 y 之间的单向道路如果 z2表示这条道路为城市 x 和城市 y 之间的双向道路。输出格式输出共 11 行包含 11 个整数表示最多能赚取的旅费。如果没有进行贸易则输出 00 。样例5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2样例输出5本题初看与最短路好不沾边为什么刚学会SPFA算法就给我们上强度啊因为我们并不关注小D走的路径长短而是关注小D走过的点的最大点权和最小点权但聪敏的你一定都能够想到既然已经规定了点大小那我们就可以通过对点的松弛操作来更新边下面我们来整理一下思路本题中有两个最值问题一起处理不太方便那我们可以将这个问题一分为二一是解决在1~x的路径中最小的点权二是解决在路径x~n中最大的点权这样才能保证求解出的差值最大。为了方便从n节点到x节点的路径遍历我们可以在完成第一次SPFA后反向建边最后我们可以依次枚举每个节点的最大值与最小值之差求出最优值。具体代码如下方#includebits/stdc.h using namespace std; typedef long long ll; const int N1e65; int n,m; ll dis1[N],v[N],dis2[N],ans0; bool vis1[N],vis2[N]; vectorintedge1[N]; vectorintedge2[N]; void spfa1(int x){//枚举1~x中路径点最小值 queueint q; q.push(x); dis1[x]v[x]; vis1[x]1; while(q.size()){ int yyq.front(); vis1[yy]0; q.pop(); for(auto i:edge1[yy]){ if(min(v[i],dis1[yy])dis1[i]){ dis1[i]min(v[i],dis1[yy]); if(!vis1[i]){ vis1[i]1; q.push(i); } } } } } void spfa2(int x){//枚举n~x中点权的最大值 queueint q; q.push(x); dis2[x]v[x]; vis2[x]1; while(q.size()){ int yyq.front(); vis2[yy]0; q.pop(); for(auto i:edge2[yy]){ if(max(v[i],dis2[yy])dis2[i]){ dis2[i]max(v[i],dis2[yy]); if(!vis2[i]){ vis2[i]1; q.push(i); } } } } } int main(){ scanf(%d%d,n,m); for(int i1;in;i) scanf(%d,v[i]); for(int i1;im;i){ int x,y,z; scanf(%d%d%d,x,y,z); edge1[x].push_back(y); edge2[y].push_back(x); if(z2){ edge1[y].push_back(x); edge2[x].push_back(y); } } memset(dis1,0x7f,sizeof(dis1));//别忘了赋初值 memset(dis2,0xef,sizeof(dis2)); //别忘了赋初值 spfa1(1);spfa2(n); for(int i1;in;i){ ansmax(ans,dis2[i]-dis1[i]); } printf(%lld,ans); }总结本次学习的最短路和最小生成树中的相关算法是在图论基础中最重要也是最不容易理解的地方一定要认真学习请记住图论的最短路有着终点但对图论的学习却是变化莫测想象无穷的 最小生成树，最短路——DAY5
今日学习为图论小进阶最小生成树和最短路两个“最”字表明这两种算法都和贪心有关不会贪心出门进我主页~~~下面我们就具体来看看这两种算法吧1.最小生成树要想了解最小生成树应如何计算首先我们要了解如何做到生成树生成树对一个具有 n 个点的连通图进行遍历对于遍历后的子图其包含原图中所有的点且保持图连通最后 的结构一定是一个具有 n-1 条边的树通常称为生成树。如图右方的两个图即为生成树了解生成树下面我们在了解一下最小生成树的操作原理对于一个无向联通图的最小生成树就是在保证所有点全部联通的情况下让每条边的边权总和尽可能的小 这就是最小生成树。等我们再次了解了最小生成树现在就上算法吧最经典的算法就是克鲁斯卡尔Kruskal算法和普利姆算法Prim这两种算法都基于贪心的思想一种是基于边权的贪心另一种则是点的贪心。克鲁斯卡尔Kruskal算法该算法初始将图视为森林图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性不构成环 的树之间建立连边。通俗来讲,我们在保证从每个点出发都能到达任意一个点的情况下将这个完全图的边权从小到大排序如下图将边权从小到大排序后 我们可以依据点的遍历情况依次在最小生成树中加边为防止在生成树中建立无效的边权从而导致最小生成树的生成我们可以判断枚举每一条边中的两个端点是否在统一集合中如果是则该边建立无效跳过反之则将边加入同时将两点并入集合中此处我们可以采用并查集的思想来做并查集的具体内容此处不在讲解~~生成后的最小生成树如下kruskal算法的具体代码如下展示#includebits/stdc.h #define ll long long #define db double #define endl \n using namespace std; const int N1e510; int f[N],vis[N],ans,n,m; struct wy{int x,y,v;}b[N]; //并查集找父亲路径压缩. inline int getf(int x) {return f[x]x?x:f[x]getf(f[x]);} //kruskal算法 inline void kruskal() { for(int i1;in;i) f[i]i; int cnt0;//记录已经是最小生成树的边 for(int i1;im;i) { //找出当前两个端点的所属的集合 int txgetf(b[i].x),tygetf(b[i].y),vb[i].v; if(tx!ty) //所属集合不同说明当前边作为最小生成树的边 { f[tx]ty; //两个集合合并 vis[i]1; //标记当前边为最小生成树边 ansv; //记录最小生成树权值和. if(cntn-1) return;//如果当前边已经达到n-1说明最小生成树已经生成无需继续查找其他边. } } }克鲁斯卡尔在解决最小生成树中应用最为广泛一定要会普里姆PRIM算法前文中提到克鲁斯卡尔算法是基于边权值的贪心而PRIM算法则是基于点的贪心在找最小生成树时将顶点分为两类一类是在查找的过程中已经包含在生成树中的顶点 假设为 A 类剩下的为另一类假设为 B 类。对于给定的连通网起始状态全部顶点都归为 B 类。在找最小生成树时选定任意一个顶点作为起始 点并将之从 B 类移至 A 类然后找出 B 类中到 A 类中的顶点之间权值最小的顶点将之从 B 类移至 A 类如此重复直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。具体实现过程我们可以用一个小根堆或是使用大根堆但将边权取负入队存入需要拓展的节点和 其边权每次取出代价最小的节点看是否在最小生成树中若不在则将其加入并且将其邻接点全部入队。当加入的点数n时返回输出答案。具体代码如下void prim(){ priority_queuekk q; q.push({0,1}); while(q.size()){ kk opq.top(); int vop.d,xxop.id; q.pop(); if(vis[xx]) continue; maxxv; cnt; vis[xx]1; if(cntn) return; for(auto i:a[xx]){ int yyi.first,vvi.second; if(!vis[yy]){ q.push({vv,yy}); } } } }下面关于最小生成树我们再来看一道例题题目描述Farmer John希望把水源引入他的N (1N3001N300) 个牧场,牧场的编号是1 ~ N.他将水源引入某个牧场的方法有两个,一个是在牧场中打一口井,另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连.在牧场i中打井的费用是Wi (1Wi100000).把牧场i和j用一根管道相连的费用是Pij (1Pij100000,PijPji, Pii0).请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源.输入格式第11行: 一个正整数N.第2 ~N1行: 第i1行包含一个正整数Wi.第N2~2N1行: 第N1i行包含N个用空格分隔的正整数,第j个数表示Pij.输出格式总共有四个牧场.在11号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要33的费用.在不同的牧场间建立管道需要2,3或4的费用.input4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0Copyoutput9本题中给出了一个邻接矩阵表示Pij修管道的费用其实也就是给出了每两点之间的一条边和其边权很容易让人想到最小生成树但本题的难点在于有一个修井的费用可以代替修管道的费用呢那该如何处理呢我们考虑假设在n号点外面有一口井n1,而修井的费用其实就是与这口大井连边问题就转化好了求n1个点的最小生成树具体核心代码如下for(int i1;in;i){ scanf(%d,a[i]); edge[bs].ui,edge[bs].vn1,edge[bs].ca[i]; } for(int i1;in;i){ for(int j1;jn;j){ int x; scanf(%d,x); if(ji) edge[bs].ui,edge[bs].vj,edge[bs].cx; } }void kruskal(){ for(int i1;in;i) f[i]i; for(int i1;ibs;i){ int xxget(edge[i].u),yyget(edge[i].v); if(xx!yy){ f[xx]yy; ansedge[i].c; if(cntn) return; } } }最短路给定一个有权图最短路径就是从一点出发到达另一点的权值之和最小的路径。最短路径的分类最短路径问题分为单源最短路径问题和多源最短路径问题单源最短路径求解的是从图中的一个顶点出发到达图中所有顶点的最短路径算法有Dijkstra算法迪杰斯特拉算法、Spfa算法。多源最短路径求解的是同一个图中任意两个顶点之间的最短路径。算法有Floyd-Warshall算法弗洛伊德算法Dijkstra算法Dijkstra算法是一种用于在加权图中寻找单源最短路径的算法。它适用于边权非负的图通过逐步扩展最短路径树来找到从源点到所有其他顶点的最短路径。算法核心思想算法维护一个集合S包含已确定最短路径的顶点以及一个优先队列或最小堆用于选择当前距离源点最近的未访问顶点。每次从优先队列中取出距离最小的顶点松弛其邻居的距离。注意事项时间复杂度为O((VE)logV)其中V是顶点数E是边数。仅适用于非负权重的图负权边需使用Bellman-Ford算法。优先队列的实现需使用小顶堆C中priority_queue默认是大顶堆需通过greater调整或者在存入时存进负边权。SPFA算法就是容易死了感兴趣的同学如果想知道它为什么死了可以详见NOI2018day1 t1归程~~~SPFA算法是我们的国产算法那让我们代入当事人的视角来详细分析一下SPFA算法在SPFA算法诞生之前应用于单源最短路径的算法只有Dijkstra算法虽然Dijkstra算法的时间复杂度很优秀但其缺点也有很多例如无法处理负边权负环等问题这使得当时算法的局限性很多但这时SPFA算法应运而生。SPFA算法基于Dijkstra算法的基础上让每个点在对点与点之间进行松弛操作后将vis数组重新标记为0保证每个点可以不断地在更新后进行松弛操作。通俗来讲再无负数的情况下3n一定严格大于2但一旦有了负数3n与2的大小关系就无法保证这时我们就需要分类讨论而 SPFA算法就是在Dijkstra算法上进行了k次分类讨论。因为有了分类讨论SPFA算法在实用性上要比Dijkstra算法要强出不少在解决负环问题上SPFA算法可以记录节点入队次数若超过|V|次则存在负权环”在解决最长路问题上SPFA可以让每个点都对其进行最长路的松弛操作从而完成对最长路的处理。它唯一其最致命的缺点就是时间复杂度不稳定为Okm),k的数值要根据图的具体形状来判断最坏的情况下SPFA的时间复杂度为Onm),当n的数值1e4时SPFA会超时限免咱们来看一道经典例题题目描述C 国有 n 个大城市和 m 条道路每条道路连接这 nn 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 mm 条道路中有一部分为单向通行的道路一部分为双向通行的道路双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔各地的资源分布情况各不相同这就导致了同一种商品在不同城市的价格不一定相同。但是同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后便决定在旅游的同时利用商品在不同城市中的差价赚回一点旅费。设 C 国 nn 个城市的标号从 1∼n阿龙决定从 1 号城市出发并最终在 n 号城市结束自己的旅行。在旅游的过程中任何城市可以重复经过多次但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费他会选择一个经过的城市买入他最喜欢的商品——水晶球并在之后经过的另一个城市卖出这个水晶球用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游他决定这个贸易只进行最多一次当然在赚不到差价的情况下他就无需进行贸易。假设 C 国有 5 个大城市城市的编号和道路连接情况如下图单向箭头表示这条道路为单向通行双向箭头表示这条道路为双向通行。假设 11 ~ nn 号城市的水晶球价格分别为 4,3,5,6,14,3,5,6,1 。阿龙可以选择如下一条线路1→2→3→5并在 22 号城市以 33 的价格买入水晶球在 33 号城市以 55 的价格卖出水晶球赚取的旅费数为 22 。阿龙也可以选择如下一条线路 1→4→5→4→5并在第 11 次到达 55 号城市时以 11 的价格买入水晶球在第 2 次到达 4 号城市时以 66 的价格卖出水晶球赚取的旅费数为 55 。现在给出 nn个城市的水晶球价格 mm 条道路的信息每条道路所连接的两个城市的编号以及该条道路的通行情况。请你告诉阿龙他最多能赚取多少旅费。输入格式输入第一行包含 2 个正整数 nn 和 mm中间用一个空格隔开分别表示城市的数目和道路的数目。第二行 nn 个正整数每两个整数之间用一个空格隔开按标号顺序分别表示这 nn 个城市的商品价格。接下来 mm 行每行有 33 个正整数 x,y,z每两个整数之间用一个空格隔开。如果 z1表示这条道路是城市 x 到城市 y 之间的单向道路如果 z2表示这条道路为城市 x 和城市 y 之间的双向道路。输出格式输出共 11 行包含 11 个整数表示最多能赚取的旅费。如果没有进行贸易则输出 00 。样例5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2样例输出5本题初看与最短路好不沾边为什么刚学会SPFA算法就给我们上强度啊因为我们并不关注小D走的路径长短而是关注小D走过的点的最大点权和最小点权但聪敏的你一定都能够想到既然已经规定了点大小那我们就可以通过对点的松弛操作来更新边下面我们来整理一下思路本题中有两个最值问题一起处理不太方便那我们可以将这个问题一分为二一是解决在1~x的路径中最小的点权二是解决在路径x~n中最大的点权这样才能保证求解出的差值最大。为了方便从n节点到x节点的路径遍历我们可以在完成第一次SPFA后反向建边最后我们可以依次枚举每个节点的最大值与最小值之差求出最优值。具体代码如下方#includebits/stdc.h using namespace std; typedef long long ll; const int N1e65; int n,m; ll dis1[N],v[N],dis2[N],ans0; bool vis1[N],vis2[N]; vectorintedge1[N]; vectorintedge2[N]; void spfa1(int x){//枚举1~x中路径点最小值 queueint q; q.push(x); dis1[x]v[x]; vis1[x]1; while(q.size()){ int yyq.front(); vis1[yy]0; q.pop(); for(auto i:edge1[yy]){ if(min(v[i],dis1[yy])dis1[i]){ dis1[i]min(v[i],dis1[yy]); if(!vis1[i]){ vis1[i]1; q.push(i); } } } } } void spfa2(int x){//枚举n~x中点权的最大值 queueint q; q.push(x); dis2[x]v[x]; vis2[x]1; while(q.size()){ int yyq.front(); vis2[yy]0; q.pop(); for(auto i:edge2[yy]){ if(max(v[i],dis2[yy])dis2[i]){ dis2[i]max(v[i],dis2[yy]); if(!vis2[i]){ vis2[i]1; q.push(i); } } } } } int main(){ scanf(%d%d,n,m); for(int i1;in;i) scanf(%d,v[i]); for(int i1;im;i){ int x,y,z; scanf(%d%d%d,x,y,z); edge1[x].push_back(y); edge2[y].push_back(x); if(z2){ edge1[y].push_back(x); edge2[x].push_back(y); } } memset(dis1,0x7f,sizeof(dis1));//别忘了赋初值 memset(dis2,0xef,sizeof(dis2)); //别忘了赋初值 spfa1(1);spfa2(n); for(int i1;in;i){ ansmax(ans,dis2[i]-dis1[i]); } printf(%lld,ans); }总结本次学习的最短路和最小生成树中的相关算法是在图论基础中最重要也是最不容易理解的地方一定要认真学习请记住图论的最短路有着终点但对图论的学习却是变化莫测想象无穷的