IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> spfa已死???(bushi) -> 正文阅读

[数据结构与算法]spfa已死???(bushi)

spfa

之前说这个spfa已经死了,但是今天看到一道题去维护变量之间额大小关系,第一想法是并查集,但是好像并查集并不可以维护查分约束的条件,所以我看了看题解,发现是我认为已经死了的spfa

思想

还是松弛,还是松弛,还是松弛,其实就是一个优化的bellman ford,本质上就是bfs去找点,只要dis大就去松弛,之后看看这个点在不在队列里,如果不在就加入队列,之后一波操作完成之后就可以的到单元最短路,其实还是很easy的
上代码

void spfa(int x){
	dis[x]=0;
	vis[x]=true;
	queue<int>q;
	q.push(q);
	while(!q.empty()){
		int g=q.front();
		q.pop();
		vis[g]=flase;
		for(int i=head[g];i;i=nex[i]){
			if(dis[to[i]]>dis[g]+val[i]){
				dis[to[i]]=dis[g]+val[i];
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=true;
				}
			}
		}
	}
}

用处----判断负环

其实这个判断主要还是在维护查分约束条件的时候去用,有些时候tarjan去找负环也是可以的而且快。

找负环的思想其实就是,可以发现,假如有负环那么是不是就会一直在这里刷最小路,所以每一个点会进入队列很多次,在没有负环的时候最多是n次,那么在这里就是只要进入了n+1次,就说明有负环
代码就是改动一下下就好

void spfa(int x){
	queue<int>q;
	q.push(x);
	dis[x]
	vis[x]=true;
	cnt[x]++; 
	while(!q.empty()){
		int g=q.front();
		q.pop();
		vis[g]=false;
		for(int i=head[g];i;i=nex[i]){
			if(dis[to[i]]>dis[g]+val[i]){
				dis[to[i]]=dis[g]+val[i];
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]==n+1){
						cout<<"No";
						return;
					}
				}
			}
		}
	}
	cout<<"Yes";
}

维护查分约束

其实就是对于 a-b>c 我去建立a->c的边大小为-b,以此类推,对于等于关系其实就是add(a,b,0),add(b,a,0)。 最后划一划就可以发现,其实有负环就说明这个条件是不合理的,为什么呢,理性的理解一下
a+b>c c+d>f
可以推出a+(b+d)>f

假如 f-(b+d+1)>a

这个条件显然是会有一个复环,并且我们发现去合并下这些不等书会出现 -1>0

显然是不合适的,所以就可以推出这个性质了,不过为了保证图的联通,我来一个超级原点n+1,他可以到达每一个点,距离为0,这样就可以去求n+1这个点的单元最短路。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=5003;
int read(){
	int r=0;
	char ch;
	ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {r=(r<<3)+(r<<1)+ch-'0';ch=getchar();}
	return r;
}


int n,m; 
int head[maxn],to[maxn],nex[maxn],val[maxn],num=0,dis[maxn];
void add(int x,int y,int z){
	to[++num]=y;
	nex[num]=head[x];
	head[x]=num;
	val[num]=z;
}

int cnt[maxn];
bool vis[maxn];
void spfa(int x){
	queue<int>q;
	q.push(x);
	dis[x]
	vis[x]=true;
	cnt[x]++; 
	while(!q.empty()){
		int g=q.front();
		q.pop();
		vis[g]=false;
		for(int i=head[g];i;i=nex[i]){
			if(dis[to[i]]>dis[g]+val[i]){
				dis[to[i]]=dis[g]+val[i];
				if(!vis[to[i]]){
					q.push(to[i]);
					vis[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]==n+1){
						cout<<"No";
						return;
					}
				}
			}
		}
	}
	cout<<"Yes";
}


int main(){
	n=read();	
	m=read();
	int a,b,c;
	for(int i=1;i<=m;i++){
		int q=read();
		if(q==1){
			a=read();b=read();c=read();
			add(a,b,-c);
		}
		if(q==2){
			a=read();b=read();c=read();
			add(b,a,c);
		}
		if(q==3){
			a=read();
			b=read();
			add(a,b,0);add(b,a,0);
		}
	}
	for(int i=1;i<=n;i++){
		add(n+1,i,0);//去避免图的不连通,所以说有一个点去作为原点
		dis[i]=maxn+1; 
	}
	spfa(n+1);
	return 0;
} 

后记

每一个算法都有存在的意义,我们不要功利的去学习,而是要去享受这个学习并运用的过程,这才是伟人去努力的原因。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-20 15:22:16  更:2021-08-20 15:22:39 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 16:50:21-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计