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