Poetic_Rain资料

本文主要介绍Poetic_Rain资料 方法和在新技术下所面对的“挑战”,方便大家深入理解Poetic_Rain资料 过程。本文也将分享Poetic_Rain资料 所遇到的问题和应对策略,怎么解决怎么做的问题。
通过深入本文可以理解代码原理,进行代码文档的下载,也可以查看相应 Demo 部署效果。

如题,这篇博客就讲一讲最短路以及其它 乱七八糟 的处理路径的问题

至于邻接表,邻接矩阵,有向边和无向边等基础概念之类的这里就不过多阐述了,不会的话建议先在其他dalao的博客或者书上面学习(请多谅解)


最短路

首先讲最短路,因为最短路比较基础,而且在图论中也应用较多,在学习了最短路只会就可以继续往后面学习了,如果您已经学习过了,可以直接跳到后面的最长路和次短路中

最短路,在一个图中,求一个地方到另一个地方的最短路径。联系到我们之前学过的广度优先搜索中,也可以处理类似的问题,所以我们先想一想广度优先搜索的一些思想——队列。所以在接下来的最短路算法中,或多或少的会涉及到队列

单源最短路径

单源最短路径,就是指在一个图中,给你一个起点(起点固定),然后终点不是固定的,求起点到任意终点的最短路径。这里会涉及到3种算法,以下用$dis[]$表示起点到任意终点的最短距离

1. Bellman-Ford算法

时间复杂度:O(nm)

给定一个图,对于图中的某一条边(x,y,z),x和y表示两个端点,z表示连接两条边的边权,如果有所有边都满足dis[y]≤dis[x]+z,则dis[]数组的值就是要求的最短路径

这个算法的流程就是基于以上的式子进行操作的:

1.扫描所有的边,如果有 d[y]>d[x]+z ,则 d[y]=d[x]+z (这也被叫做松弛操作) 2.重复以上的操作,知道所有边无法进行松弛操作  

还是比较好理解的,这里就不挂上代码了,因为讲这个算法的目的是为了下一个算法作铺垫

2. SPFA算法

时间复杂度:O(km) (k为一个较小的常数)

SPFA算法其实就是用队列优化过后的Ford的算法,所以没事别用Ford算法 ,所以它的算法实现和Ford算法其实是有相似之处的:

1.建立队列,起初队列中的节点只有起点 2.取出队头的点 x ,然后扫描 x 的所有出边(x,y,z)进行松弛操作,如果 y 不在队列中,将 y 入队  3.重复以上操作,直到队列为空  

——分割线,下面是代码——

int head[MAXN],tot; struct edge{ 	int net,to,w; }e[MAXN]; void add(int x,int y,int z){ 	e[++tot].net=head[x]; 	e[tot].to=y; 	e[tot].w=z; 	head[x]=tot; }  //以上是链式前向星的建边 bool v[MAXN]; //是否入队  int dis[MAXN],vis[MAXN]; //dis为最短距离,vis为入队次数,如果入队次数太多,说明该图中有环  queue<int>q; //队列  bool spfa(int s){ 	for(register int i=1;i<=n;i++) dis[i]=INF,v[i]=false; //初始化  	d[s]=0,v[s]=true; 	vis[s]++; 	q.push(s); 	while(!q.empty()){ 		int x=q.front(); 		q.pop(); //取出队头  		v[x]=false; 		if(vis[x]>n) return false; //超过了n次,就说明有环  		for(register int i=head[x];i;i=e[i].net){ //扫描x的出边  			int y=e[i].to,z=e[i].w; 			if(d[y]>d[x]+z){ //松弛操作  				d[y]=d[x]+z; 				if(v[y]==false){ //是否入队  					v[y]=true; 					vis[y]++; 					q.push(y); 				} 			} 		} 	} 	return true; }  

相信大家都听说过流传于OI界的一句话“关于SPFA,它死了”,是因为有的出题人故意出数据卡SPFA,所以SPFA的时间复杂度会退化为Ford,所以在下面又会介绍一种超级香的算法

3. Dijkstra算法

SPFA已死,Dijkstra当立!!!

这里先讲DIjkstra的算法流程:

1.初始化dis[]为极大值,起点为0 2.找出一个没有被标记过的且dis[]值最小的节点x,然后标记点x 3.扫描x的出边,进行松弛操作 4.重复以上步骤,直到所有点都被标记  

这里不难看出Dijkstra是基于贪心思想的一种最短路算法,我们通过一个已经确定了的最短路$dis[x]$,然后不断找到全局最小值进行标记和扩展,最终实现算法,其实对于以上的步骤,也可以进行一个堆优化(优先队列优化),所以下面我会给出两个程序段

未优化 时间复杂度:O(n^2)

int dis[MAXN]; bool v[MAXN]; void Dijkstra(int s){ 	for(register int i=1;i<=n;i++) dis[i]=INF,v[i]=false; 	d[s]=0;  //初始化  	for(register int i=1;i<n;i++){ 		int x=0; 		for(register int j=1;j<=n;j++){ 			if(v[j]==false&&(x==0||d[j]<d[x])) x=j; 		} //找到最小的x  		v[x]=true; 		for(register int y=1;y<=n;y++){ 			d[y]=min(d[y],d[x]+a[x][y]); 		} //松弛操作  	} } ··· ··· for(register int i=1;i<=n;i++){ 	for(register int j=1;j<=n;j++){ 		a[i][j]=INF; 	} 	a[i][i]=0; }  for(register int i=1;i<=m;i++){ 	int x,y,z; 	a[x][y]=min(a[x][y],z); //取min是为了判断重边  } //建立邻接矩阵  

堆优化 时间复杂度:O(m log n)

int head[MAXN],tot; struct edge{ 	int net,to,w; }e[MAXN]; void add(int x,int y,int z){ 	e[++tot].net=head[x]; 	e[tot].to=y; 	e[tot].w=z; 	head[x]=tot; } //邻接表建边 int d[MAXN]; bool v[MAXN]; priority_queue<pair<int,int> >q; //这里是建大根堆,利用相反数实现小根堆 //first为距离,second为编号 //按first从小到大排序  //或者你自己手写重载运算符  void Dijkstra(int s){ 	for(register int i=1;i<=n;i++) d[i]=INF,v[i]=false; 	d[s]=0; 	q.push(make_pair(0,s)); 	while(!q.empty()){ 		int x=q.top().second; 		q.pop(); 		if(v[x]==true) continue; 		v[x]=true; 		for(register int i=head[x];i;i=e[i].net){ 			int y=e[i].to,z=e[i].w; 			if(d[y]>d[x]+z){ 				d[y]=d[x]+z; 				q.push(make_pair(-d[y],y)); 				//非常灵魂的取相反数  			} 		}  	}  } 

关于Dijkstra,它是真的很香,因为确实跑得很快,对于单源最短路的算法就介绍到这里了,但是对于这些算法的各自特点,我会留到最后来讲

多源最短路径

目前涉及到的还只有FLoyd算法,当然还有一个Johnson的全源最短路算法,因为用的不多,这里就不过多介绍

Floyd算法

时间复杂度:O(n^3)

对于Floyd的实现,其实非常的简单,它有一点像动态规划的方式,通过枚举所有中间点进行松弛操作,大概就是在直接路径和间接路径中取一个最小的,这里就直接挂上代码了

for(register int i=1;i<=n;i++){ 	for(register int j=1;j<=n;j++){ 		d[i][j]=INF; 	} 	d[i][i]=0; }//邻接矩阵存储,d[i][j]表示i到j的距离  for(register int k=1;k<=n;k++){ //第一层枚举中间点  	for(register int i=1;i<=n;i++){ //第二层枚举起点  		for(register int j=1;j<=n;j++){ //第三层枚举终点  			if(i!=j&&j!=k) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);  			//动态转移方程,在间接路径和直接路径中取最小值  		} 	} } 

总结

以上就是对于最短路的算法介绍,这里会对各种算法进行对比和总结,然后给出一些我个人认为好一点的例题

首先是Ford算法,不用说,能不用就别用,因为SPFA算法在大部分时候都比Ford算法优越,最多就和Ford算法一样

然后说SPFA,SPFA其实可以处理负边权和负环的情况,这是它的特点,而SPFA在不被卡的情况下其实是比Dijkstra更加快的(但是SPFA基本上都会被卡的死死的)

过了就是DIjkstra,这个算法其实算是可以优先选择,但是遇到环和负边权的情况,它是完全不能处理的,这个时候就要回去考虑SPFA了

对于FLoyd,如果不是多源最短路就可以不考虑,因为二维数组的空间不会太大,并且n^3的时间复杂度估计没人会接受吧,但是Floyd(Floyd的变种)有一些其它的应用,这里不会涉及

先上两道通用的模板题

第二道其实完全可以不考虑,但是还是要放一下,这样你们才能自己亲身感受一下上面各类算法的区别,建议大家各种算法都试一试(SPFA真的死得特别惨)

P4779 【模板】单源最短路径(标准版)

P3371 【模板】单源最短路径(弱化版)

然后就是其它的一些单独的算法了:

Dijkstra

P1396 营救

P5651 基础最短路练习题

P1529 [USACO2.4]回家 Bessie Come Home

P1629 邮递员送信

这几道题中,邮递员送信会涉及到一点反向图的知识,可以去看我的另一篇博客(啊。无耻)。回家那道题难在一些字符串的处理上。剩下两道题就比较模板了,考验大家对算法的本质的一些认识

SPFA

P1938 [USACO09NOV]Job Hunt S

我是真的没有找到几道必须用SPFA做的题,所以大家见谅啊,但是所有能用Dijkstra的都可以用SPFA,但是一般会被卡。。。这道题难在处理点权和边权的关系上面

Floyd

P1364 医院设置

P1119 灾后重建

P1522 [USACO2.4]牛的旅行 Cow Tours

如果你能自己A掉上面的题,证明你对Floyd的理解已经很深很透彻了,所以在思维难度上是比较高的

最短路的综合练习

P1608 路径统计

P1144 最短路计数

P1186 玛丽卡

这三道题就是用来告诉你如何记录最短路的路径的,为之后的次短路的算法作一下铺垫吧,顺便加深理解。这里就不放代码了,如果不会的话可以去看看我的博客或者其他dalao的题解


最长路

最长路,顾名思义嘛,最短路就是道路最短,那就最长路就是道路最长了咯

最长路的求法也有两种,一种是SPFA,一种是拓扑排序,拓扑排序跑得比SPFA快很多,这里也要说一下,虽然SPFA容易被卡,但是希望那些认为SPFA没用的人也去学一学,这是很有必要的(尽管我知道用SPFA的人很多

首先讲SPFA,我们知道SPFA算法可以处理负边权的问题,如果你上过小学,那么你肯定知道,一个负数越小,那它的绝对值肯定更大。这样我们就可以把最长路问题转换为最短路问题了

相比读者肯定已经想到了,在存边的时候,我们只需要把边权取一个相反数,然后正常地求最短路,在最后的答案中取一个相反数就可以了,是不是很简单?

然后是拓扑排序,不知道或是不了解拓扑排序的可以看一下这篇博客(继续无耻),同桌的拓扑排序

了解拓扑排序之后,我们其实可以知道使用拓扑排序的话是有限制的,它只能处理有向无环图,无向图这些都不能处理,但是还是要去学。使用拓扑排序的话,需要用到一些DP的思想,这个地方不太好讲解思路,直接在代码里面看实现方法

这里就直接用一个例题来讲解了

P1807 最长路

SPFA

#include <bits/stdc++.h> using namespace std; int n,m,u,v,w,tot; int dis[510010],vis[510010],head[510010];  struct node { 	int to,net,val; } e[510010];  inline void add(int u,int v,int w) { 	e[++tot].to=v; 	e[tot].net=head[u]; 	e[tot].val=w; 	head[u]=tot; } //链式前向星建边  inline void spfa() { 	queue<int> q; 	for(register int i=1;i<=n;i++) dis[i]=20050206; 	dis[1]=0; 	vis[1]=1; 	q.push(1); 	while(!q.empty()) { 		int x=q.front(); 		q.pop(); 		vis[x]=0; 		for(register int i=head[x];i;i=e[i].net) { 			int v=e[i].to; 			if(dis[v]>dis[x]+e[i].val) { 				dis[v]=dis[x]+e[i].val; 				if(!vis[v]) { 					vis[v]=1; 					q.push(v); 				} 			} 		} 	} }//正常跑最短路   int main() { 	scanf("%d%d",&n,&m); 	for(register int i=1;i<=m;i++) { 		scanf("%d%d%d",&u,&v,&w); 		add(u,v,-w);//非常灵魂地存一个相反数  	} 	spfa(); 	if(dis[n]==20050206) puts("-1"); //到不了就-1  	else printf("%d",-dis[n]);//记得存回来  	return 0; } 

拓扑排序

#include<bits/stdc++.h> using namespace std; const int MAXN=2*5*1e4; int n,m; struct edge{ 	int net,to,w; }e[MAXN]; int head[MAXN],tot; void add(int x,int y,int z){ 	e[++tot].net=head[x]; 	e[tot].to=y; 	e[tot].w=z; 	head[x]=tot; } //链式前向星建边  bool v[MAXN]; //用来标记是否可以从1走到这个点 //因为是1到n,所以如果不能从1开始走 //说明不满足条件,没有这条最长路  int ru[MAXN]; int ans[MAXN]; queue<int>q; void toop(){ 	for(register int i=1;i<=n;i++){ 		if(ru[i]==0) q.push(i); 	}//入度为0的进队  	while(!q.empty()){ 		int x=q.front(); 		q.pop();//出队  		for(register int i=head[x];i;i=e[i].net){ 			int y=e[i].to,z=e[i].w; 			ru[y]--;//入度--  			if(v[x]==true){ 				ans[y]=max(ans[y],ans[x]+z); 				v[y]=true; 			}//如果这个节点能从1走到,说明它的边可以走 			//更新最长路  			if(ru[y]==0) q.push(y);//进队  		} 	} } int main(){ 	scanf("%d%d",&n,&m); 	for(register int i=1;i<=m;i++){ 		int u,v,w; 		scanf("%d%d%d",&u,&v,&w); 		add(u,v,w); 		ru[v]++; 	}//建边,入度++  	v[1]=true;//1肯定自己能走  	ans[n]=-1;//初始值为-1,方便输出  	toop();//拓扑排序求最长路  	cout<<ans[n]; 	return 0; } 

最长路的其他题

P1113 杂务

P6145 [USACO20FEB]Timeline G


次短路

有了最短路和最长路,那么肯定就有次短路,还是很好理解的,就是第二短路(除了最短路的最短路)

这里的话,我就只介绍一种方法了,还有一个A star算法 这貌似都可以用来做K短路了,我想都不敢想(好吧,单纯就是我不会,如果我学会了我会回来更的)

简明扼要的来说,我们求次短路,肯定和最短路脱不了干系,所以怎么说要先把最短路跑出来,这样才能有一个拿来比较的东西

次短路,它肯定比最短路要长(废话),考虑一种非常极端的情况,次短路肯定不会是最短路(废话),那么次短路肯定至少有一条边不在最短路上,明白这个很重要,当然它也可能是完全没有交集的两条边

了解之后,我们来想想到底怎么实现这个次短路。由上面的推断,我们肯定需要去记录最短路的路径和经过的节点,如果你无法理解这个东西,可以去上面找一找玛丽卡和最短路计数两题

我们可以尝试把最短路上的任意一条边删掉,然后重新跑最短路,这样就可以保证了我之后跑的所有最短路都比第一次的最短路要长,然后通过比较就可以求出次短路了,我们通过一道例题来具体理解一下

P1491 集合位置

这道题还是比较模板,其它次短路的题我并没有接触过多少,所以还是读者自己去领悟和多刷题(见谅)

拿到这道题后,肯定先把建边这些不那么重要的东西先处理掉,记得用double和一些精度处理,所有的边和存储答案都用double。然后按上面讲的思路实现一遍

跑最短路 -> 记录路径 -> 枚举删边,再跑最短路 -> 处理答案

但其实题目中还告诉了一些条件,就是关于一些无解的判断

这其实是很好理解的,如果存在多条最短路径,那我在枚举删除第一条最短路上的边的时候,是完全不影响其它最短路的,那么我们求出来的还是一条最短路,过掉

如果不存在第二短路径,说明起点和终点之间只存在一条简单路径,而这条路径就是最短路,如果删去边之后就无法到达终点了,特判一下就ok

那么思路就这么讲完了,我们直接用代码来加深理解一下

#include<bits/stdc++.h> using namespace std; const int MAXN=1e7+50; const double INF=200500305; int n,m; int x[MAXN],y[MAXN]; struct node{ 	int net,to,from; 	double w; }e[MAXN]; int head[MAXN],tot; void add(int u,int v,double w){ 	e[++tot].net=head[u]; 	e[tot].to=v; 	e[tot].from=u; 	//这里的from和to表示这一条边的两个端点 	//在后面的程序中用来比较求次短路  	e[tot].w=w; 	head[u]=tot; } //链式前向星建边  double d[MAXN]; int bian[MAXN]; //记录最短路  bool v[MAXN]; inline bool ok(int i,int j){ 	if(min(e[i].to,e[i].from)==min(e[j].to,e[j].from)&&max(e[i].to,e[i].from)==max(e[j].to,e[j].from))return 0; 	return 1; }//这一坨长长的东西用来判断是不是我这次要删掉的边  void dij(int s,int p){ //p用来表示删除哪一条边  	priority_queue<pair<double,int> >q; 	for(register int i=1;i<=n;i++) d[i]=INF,v[i]=false; 	d[s]=0; //初始化  	q.push(make_pair(0,s)); 	while(!q.empty()){ 		int x=q.top().second; 		q.pop(); 		if(v[x]==true) continue; 		v[x]=true; 		for(register int i=head[x];i;i=e[i].net) 		if(p==-1||ok(i,p)){  //如果是第一次跑最短路就记录路径,如果是该边被删去就不跑  			int y=e[i].to; 			double z=e[i].w; 			if(d[y]>d[x]+z){ 				d[y]=d[x]+z; 				if(p==-1)bian[y]=i; //第一次跑最短路记录路径  				q.push(make_pair(-d[y],y)); 			} 		} 	} } double Min(double x,double y){ 	if(x<=y) return x; 	return y; } //c++自带的min不支持double类型的比较  int main(){ 	scanf("%d%d",&n,&m); 	for(register int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); 	for(register int i=1;i<=m;i++){ 		int u,v; 		double w; 		scanf("%d%d",&u,&v); 		w=(double)sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v])); 		add(u,v,w); 		add(v,u,w); 	}//建双向变  	dij(1,-1); //第一次跑最短路不删边  	int t=n; //用t来代替n,遍历最短路的边  	double ans=INF;  	while(t!=1){ 		int i=bian[t]; 		dij(1,i); 		ans=min(ans,d[n]); //取一个更小的答案表示次短路  		t=e[bian[t]].from; //遍历最短路的路径  	} 	printf("%.2lf",ans); //输出答案  	return 0; } 

博客园的话,我不太会用Markdown,所以我把洛谷博客也挂在这里

感谢一下ZJY,同桌和RHL三位大佬提供的一些帮助啊

这篇博客就写到这里了,如果我误人子弟了,可以在评论区指出错误或者在QQ上告诉我,我会尽早改正,这么长的文章,谢谢阅读

Poetic_Rain资料部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » Poetic_Rain资料

提供最优质的资源集合

立即查看 了解详情