企业官网建设流程全解析

今日学习为图论小进阶，最小生成树和最短路，两个“最”字表明这两种算法都和贪心有关，（不会贪心出门进我主页~~~），下面我们就具体来看看这两种算法吧！！

1.最小生成树

要想了解最小生成树应如何计算，首先我们要了解如何做到生成树，生成树：对一个具有 n 个点的连通图进行遍历，对于遍历后的子图，其包含原图中所有的点且保持图连通，最后 的结构一定是一个具有 n-1 条边的树，通常称为生成树。

如图，右方的两个图即为生成树

了解生成树，下面我们在了解一下最小生成树的操作原理，对于一个无向联通图的最小生成树，就是在保证所有点全部联通的情况下让每条边的边权总和尽可能的小， 这就是最小生成树。

等我们再次了解了最小生成树，现在就上算法吧！最经典的算法就是克鲁斯卡尔（Kruskal）算法和普利姆算法（Prim）这两种算法都基于贪心的思想，一种是基于边权的贪心，另一种则是点的贪心。

克鲁斯卡尔（Kruskal）算法

该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环） 的树之间建立连边。通俗来讲,我们在保证从每个点出发都能到达任意一个点的情况下，将这个完全图的边权从小到大排序，如下图：

将边权从小到大排序后 ，我们可以依据点的遍历情况，依次在最小生成树中加边，为防止在生成树中建立无效的边权，从而导致最小生成树的生成，我们可以判断枚举每一条边中的两个端点是否在统一集合中，如果是，则该边建立无效，跳过；反之，则将边加入，同时将两点并入集合中；此处我们可以采用并查集的思想来做，并查集的具体内容此处不在讲解~~生成后的最小生成树如下：

kruskal算法的具体代码如下展示：

#include<bits/stdc++.h> #define ll long long #define db double #define endl '\n' using namespace std; const int N=1e5+10; 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 i=1;i<=n;++i) f[i]=i; int cnt=0;//记录已经是最小生成树的边 for(int i=1;i<=m;++i) { //找出当前两个端点的所属的集合 int tx=getf(b[i].x),ty=getf(b[i].y),v=b[i].v; if(tx!=ty) //所属集合不同，说明当前边作为最小生成树的边 { f[tx]=ty; //两个集合合并 vis[i]=1; //标记当前边为最小生成树边 ans+=v; //记录最小生成树权值和. if(++cnt==n-1) return;//如果当前边已经达到n-1，说明最小生成树已经生成，无需继续查找其他边. } } }

克鲁斯卡尔在解决最小生成树中应用最为广泛，一定要会！！

普里姆（PRIM）算法

前文中提到克鲁斯卡尔算法是基于边权值的贪心，而PRIM算法则是基于点的贪心，在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在生成树中的顶点 （假设为 A 类），剩下的为另一类（假设为 B 类）。

对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始 点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

具体实现过程，我们可以用一个小根堆（或是使用大根堆但将边权取负入队），存入需要拓展的节点和 其边权，每次取出代价最小的节点，看是否在最小生成树中，若不在，则将其加入，并且将其邻接点全部入队。当加入的点数==n时，返回输出答案。具体代码如下：

void prim(){ priority_queue<kk> q; q.push({0,1}); while(q.size()){ kk op=q.top(); int v=op.d,xx=op.id; q.pop(); if(vis[xx]) continue; maxx+=v; cnt++; vis[xx]=1; if(cnt==n) return; for(auto i:a[xx]){ int yy=i.first,vv=i.second; if(!vis[yy]){ q.push({vv,yy}); } } } }

下面关于最小生成树，我们再来看一道例题：

题目描述

Farmer John希望把水源引入他的N (1<=N<=3001<=N<=300) 个牧场,牧场的编号是1 ~ N.他将水源引入某个牧场的方法有两个,一个是在牧场中打一口井,另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连.

在牧场i中打井的费用是Wi​ (1<=Wi​<=100000).

把牧场i和j用一根管道相连的费用是Pij​ (1<=Pij​<=100000,Pij​=Pji​, Pii​=0).

请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源.

输入格式

• 第11行: 一个正整数N.

• 第2 ~N+1行: 第i+1行包含一个正整数Wi​.

• 第N+2~2N+1行: 第N+1+i行包含N个用空格分隔的正整数,第j个数表示Pij​.

输出格式

总共有四个牧场.在11号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要33的费用.在不同的牧场间建立管道需要2,3或4的费用.

input

4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0

Copy

output

9

本题中给出了一个邻接矩阵，表示Pij修管道的费用，其实也就是给出了每两点之间的一条边和其边权，很容易让人想到最小生成树，但本题的难点在于有一个修井的费用，可以代替修管道的费用，呢那该如何处理呢？

我们考虑假设在n号点外面有一口井n+1,而修井的费用其实就是与这口大井连边，问题就转化好了，求n+1个点的最小生成树，具体核心代码如下：

for(int i=1;i<=n;i++){ scanf("%d",&a[i]); edge[++bs].u=i,edge[bs].v=n+1,edge[bs].c=a[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int x; scanf("%d",&x); if(j<i) edge[++bs].u=i,edge[bs].v=j,edge[bs].c=x; } }

void kruskal(){ for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=bs;i++){ int xx=get(edge[i].u),yy=get(edge[i].v); if(xx!=yy){ f[xx]=yy; ans+=edge[i].c; if(++cnt==n) return; } } }

最短路

给定一个有权图，最短路径就是从一点出发到达另一点的权值之和最小的路径。

最短路径的分类：

• 最短路径问题分为单源最短路径问题和多源最短路径问题

• 单源最短路径求解的是从图中的一个顶点出发，到达图中所有顶点的最短路径，算法有Dijkstra算法（迪杰斯特拉算法）、Spfa算法。

• 多源最短路径求解的是同一个图中，任意两个顶点之间的最短路径。算法有Floyd-Warshall算法（弗洛伊德算法）

Dijkstra算法

Dijkstra算法是一种用于在加权图中寻找单源最短路径的算法。它适用于边权非负的图，通过逐步扩展最短路径树来找到从源点到所有其他顶点的最短路径。

算法核心思想：算法维护一个集合S，包含已确定最短路径的顶点，以及一个优先队列（或最小堆），用于选择当前距离源点最近的未访问顶点。每次从优先队列中取出距离最小的顶点，松弛其邻居的距离。

注意事项

• 时间复杂度为O((V+E)logV)，其中V是顶点数，E是边数。
• 仅适用于非负权重的图，负权边需使用Bellman-Ford算法。
• 优先队列的实现需使用小顶堆，C++中priority_queue默认是大顶堆，需通过greater调整，或者在存入时存进负边权。

SPFA算法（就是容易死了）

感兴趣的同学如果想知道它为什么死了，可以详见NOI2018，day1 t1归程~~~

SPFA算法是我们的国产算法，那让我们代入当事人的视角，来详细分析一下SPFA算法

在SPFA算法诞生之前，应用于单源最短路径的算法只有Dijkstra算法，虽然Dijkstra算法的时间复杂度很优秀，但其缺点也有很多，例如无法处理负边权，负环等问题，这使得当时算法的局限性很多，但这时，SPFA算法应运而生。

SPFA算法基于Dijkstra算法的基础上，让每个点在对点与点之间进行松弛操作后，将vis数组重新标记为0，保证每个点可以不断地在更新后进行松弛操作。

通俗来讲，再无负数的情况下3+n一定严格大于2，但一旦有了负数，3+n与2的大小关系就无法保证，这时我们就需要分类讨论，而 SPFA算法就是在Dijkstra算法上进行了k次分类讨论。

因为有了分类讨论，SPFA算法在实用性上要比Dijkstra算法要强出不少，在解决负环问题上，SPFA算法可以记录节点入队次数，若超过|V|次则存在负权环”，在解决最长路问题上，SPFA可以让每个点都对其进行最长路的松弛操作，从而完成对最长路的处理。它唯一其最致命的缺点就是时间复杂度不稳定，为O（km),k的数值要根据图的具体形状来判断，最坏的情况下，SPFA的时间复杂度为O（nm),当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，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 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. 本题中有两个最值问题，一起处理不太方便，那我们可以将这个问题一分为二，一是解决在1~x的路径中最小的点权，二是解决在路径x~n中最大的点权，这样才能保证求解出的差值最大。
2. 为了方便从n节点到x节点的路径遍历，我们可以在完成第一次SPFA后反向建边
3. 最后我们可以依次枚举每个节点的最大值与最小值之差，求出最优值。

具体代码如下方：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; int n,m; ll dis1[N],v[N],dis2[N],ans=0; bool vis1[N],vis2[N]; vector<int>edge1[N]; vector<int>edge2[N]; void spfa1(int x){//枚举1~x中路径点最小值 queue<int> q; q.push(x); dis1[x]=v[x]; vis1[x]=1; while(q.size()){ int yy=q.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中点权的最大值 queue<int> q; q.push(x); dis2[x]=v[x]; vis2[x]=1; while(q.size()){ int yy=q.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 i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); edge1[x].push_back(y); edge2[y].push_back(x); if(z==2){ 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 i=1;i<=n;i++){ ans=max(ans,dis2[i]-dis1[i]); } printf("%lld",ans); }

总结

本次学习的最短路和最小生成树中的相关算法，是在图论基础中最重要也是最不容易理解的地方，一定要认真学习，请记住：

图论的最短路有着终点，但对图论的学习却是变化莫测，想象无穷的！！！