洛谷P1993 小K的农场_差分约束_dfs跑SPFA
2024-08-30 02:09:20
Code:
#include<cstdio>
#include<queue>
using namespace std;
const int N=10000+233;
const int INF=10000000;
int head[N],to[N<<1],nex[N<<1],val[N<<1],vis[N],d[N];
int cnt;
void add_edge(int u,int v,int c)
{
nex[++cnt]=head[u],head[u]=cnt;
to[cnt]=v,val[cnt]=c;
}
int spfa(int u)
{
vis[u]=1;
for(int v=head[u];v;v=nex[v])
{
int x=to[v];
if(d[u]+val[v]<d[x])
{
d[x]=d[u]+val[v];
if(vis[x]==1)return 0;
if(spfa(x)==0)return 0;
}
}
vis[u]=0;
return 1;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)d[i]=INF;
for(int i=1;i<=m;++i)
{
int Ty,a,b,c;
scanf("%d%d%d",&Ty,&a,&b);
if(Ty!=3)scanf("%d",&c);
if(Ty==1)
add_edge(a,b,-c);
if(Ty==2)
add_edge(b,a,c);
if(Ty==3)
{
c=0;
add_edge(b,a,c);
add_edge(a,b,-c);
}
}
int ans=1;
for(int i=1;i<=n;++i)
{
if(vis[i]==0)
if(!spfa(i))
{
ans=0;break;
}
}
if(ans==0)printf("No");
else printf("Yes");
return 0;
}
最新文章
- HTML5打造的炫酷本地音乐播放器-喵喵Player
- git的配置
- C#的参数修饰符out,params,ref
- [Html5]sessionStorage和localStorage常见操作
- TfS+强制删除签出锁定项
- 124. Binary Tree Maximum Path Sum
- poj 1016 Numbers That Count
- mybatis源码学习: 编译的方法
- c#代码使用ResourceDictionary样式
- Python自动化运维之20、HTML
- [Python笔记][第一章Python基础]
- 内容中断随想录(risc cpu的那些事)
- apache 做负载
- 对象this的引用
- [field:softlinks/]逻辑过程
- js—双等号引起的类型转换过程
- Autofac之依赖注入
- 【MySQL】InnoDB 内存管理机制 --- Buffer Pool
- HTTP Method小结
- python自动化开发-5a
热门文章
- 百度之星2014复赛 - 1001 - Find Numbers
- swift 笔记 (十四) —— 构造过程
- _DataStructure_C_Impl:基数排序
- Coco2d-js/Cocos2d-html5中Android返回键实现
- 关于SharePoint讨论板的一些知识(2)--视图中的栏目
- nexus启动报错----->;错误 1067: 进程意外终止。
- Swift - 将String类型的数字转换成数字类型(支持十进制、十六进制)
- DNS隧道工具使用 不过其网络传输速度限制较大
- Spring版本功能变更&;Spring4.x的新特性
- 2017-3-10 leetcode 229 238 268