博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
spfa判负权边
阅读量:5879 次
发布时间:2019-06-19

本文共 999 字,大约阅读时间需要 3 分钟。

spfa判负环

如果一个点在spfa中被入队了大于n次

那么,我们就能肯定,有负环出现。

因为一个点入队时,他肯定被更新了一次。

所以........ 如果不存在负权环。这个点最多被更新节点数次

我们就可以利用这个性质判负环

亏我dijk写了一上午

语文模板题

#include
#include
#include
#include
#include
using namespace std;int dis[11000];struct L{ int point; int weight; int nxt;};L line[100000];int head[10000],tail;bool exist[100000];int inque[100000];queue
q;int n,m;void add(int x,int y,int val){ line[++tail].point=y; line[tail].weight=val; line[tail].nxt=head[x]; head[x]=tail;}void spfa(int begin){ memset(dis,0x3f,sizeof(dis)); memset(exist,0,sizeof(exist)); dis[begin]=0; exist[begin]=true; inque[begin]+=1; q.push(begin); int pass; while(!q.empty()) { pass=q.front(); q.pop(); exist[pass]=false; if(inque[pass]>n) { printf("Forever love"); exit(0); } for(int need=head[pass];need;need=line[need].nxt) if(dis[pass]+line[need].weight

转载于:https://www.cnblogs.com/Lance1ot/p/8639194.html

你可能感兴趣的文章
前端工程化系列[01]-Bower包管理工具的使用
查看>>
使用 maven 自动将源码打包并发布
查看>>
Spark:求出分组内的TopN
查看>>
Python爬取豆瓣《复仇者联盟3》评论并生成乖萌的格鲁特
查看>>
关于跨DB增量(增、改)同步两张表的数据小技巧
查看>>
学员会诊之03:你那惨不忍睹的三层架构
查看>>
vue-04-组件
查看>>
Golang协程与通道整理
查看>>
解决win7远程桌面连接时发生身份验证错误的方法
查看>>
C/C++ 多线程机制
查看>>
js - object.assign 以及浅、深拷贝
查看>>
python mysql Connect Pool mysql连接池 (201
查看>>
Boost在vs2010下的配置
查看>>
一起谈.NET技术,ASP.NET伪静态的实现及伪静态的意义
查看>>
20款绝佳的HTML5应用程序示例
查看>>
string::c_str()、string::c_data()及string与char *的正确转换
查看>>
11G数据的hive初测试
查看>>
如何使用Core Text计算一段文本绘制在屏幕上之后的高度
查看>>
==和equals区别
查看>>
2010技术应用计划
查看>>