差分约束+spfa判负环

dfs判负环

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define dec(i,x,y) for(register int i=x;i>=y;i--)
#define ll long long
using namespace std; const int N=;
const int inf=0x3f3f3f3f; int dis[N],vis[N],head[N],tot;
struct node{int v,w,next;}e[N];
void insert(int u,int v,int w){
e[++tot]=(node){v,w,head[u]};head[u]=tot;} inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
int n,m,ch,a,b,c; inline int spfa(int u){
vis[u]=;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v,w=e[i].w;
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;
if(vis[v]) return ;
if(!spfa(v)) return ;
}
}
vis[u]=;
return ;
} int main(){
n=read();m=read();
while(m--){
ch=read();a=read();b=read();
if(ch==) c=read(),insert(b,a,c);
else if(ch==) c=read(),insert(a,b,-c);
else if(ch==) insert(a,b,),insert(b,a,);
}rep(i,,n) insert(,i,),dis[i]=-inf;
if(!spfa()) printf("No");
else printf("Yes");
return ;
}

最新文章

  1. linux下安装启动rpc服务
  2. 关于模拟http请求 cookie的赋值
  3. Atitit 混合叠加俩张图片的处理 图像处理解决方案 javafx blend
  4. Dispose() C# 优化内存
  5. Android俄罗斯方块AI设计文档
  6. 【227】◀▶ IDL 其他常用函数
  7. Javascript中日期函数的相关操作
  8. [置顶] c++,vc6.0,中友元函数,无法访问私有字段(private)的问题(problem),cannot access private member declared in class &#39;Date&#39;
  9. Python函数返回不定数量的值
  10. django 开发忘记密码通过邮箱找回功能
  11. That girl
  12. [Swift]LeetCode179. 最大数 | Largest Number
  13. vue的一些基本知识
  14. tomcat守护相关
  15. 一、VScode构建.NET应用程序
  16. 我所知道的JS调试
  17. ThinkPHP3.1快速入门教程
  18. 数据结构(C语言版)-C语言和C++相关补充
  19. ArrayList的源码分析
  20. SQL Server中使用自定义指定顺序排序

热门文章

  1. free命令详解
  2. python之匿名函数lambda
  3. IBM推出新一代云计算技术来解决多云管理
  4. Spring AOP动态代理原理与实现方式
  5. ACM-ICPC 2018 焦作赛区网络预赛 E Jiu Yuan Wants to Eat (树链剖分+线段树)
  6. 【 Gym 101116K 】Mixing Bowls(dfs)
  7. luogu P2644 树上游戏
  8. Android canvast View 代码实例
  9. Java 关键字final的一小结
  10. 【SDOI 2017】龙与地下城(组合)