bzoj3436小K的农场

题意:

n个数,知道m条关系:a-b≥c、a-b≤c或a==b。问是否存在满足所有关系的情况。n≤10000,m≤10000。

题解:

差分约束。因为只要求是否满足,因此最短路最长路都可以。不过要注意如果是用spfa的bfs写法,每个点都必须作为源点判一次负环,因为图可能不连通。正因为如此,虽说加了SLF的bfs写法spfa能卡过,但比dfs写法慢不只10倍。

代码:

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
} struct e{int t,w,n;}; e es[maxn*]; int g[maxn],ess;
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int n,m,cnt[maxn],d[maxn]; bool inq[maxn]; deque<int>q;
ll spfa(int s){
q.clear(); memset(inq,,sizeof(inq)); memset(cnt,,sizeof(cnt));
q.push_back(s); inq[s]=; d[s]=; cnt[s]=;
while(!q.empty()){
int x=q.front(); q.pop_front(); inq[x]=;
for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
d[es[i].t]=d[x]+es[i].w;
if(!inq[es[i].t]){
if(!q.empty()&&d[es[i].t]<d[q.front()])q.push_front(es[i].t);else q.push_back(es[i].t);
inq[es[i].t]=; cnt[es[i].t]++; if(cnt[es[i].t]>=n)return ;
}
}
}
return ;
}
int main(){
n=read(); m=read();
inc(i,,m){
int opt=read(),a,b,c;
if(opt==)a=read(),b=read(),c=read(),pe(a,b,-c);
if(opt==)a=read(),b=read(),c=read(),pe(b,a,c);
if(opt==)a=read(),b=read(),pe(b,a,),pe(a,b,);
}
inc(i,,n)if(!spfa(i)){puts("No"); return ;} puts("Yes"); return ;
}

20161018

最新文章

  1. v$session中server为none与shared值解析
  2. 自定义RatingBar的一个问题(只显示显示一个星星)
  3. 【CodeVS2800】 送外卖 最短路+状压DP
  4. 20151011 C# 第一篇 运算符
  5. Biee 迁移和刷新GUIDs
  6. DateUtils
  7. Codeforces 733C:Epidemic in Monstropolis(暴力贪心)
  8. CollectionsAPI
  9. [Spring] IOC - study
  10. 洛谷P1204 [USACO1.2]挤牛奶Milking Cows
  11. Arrays类与Array类探究
  12. 6.python内置函数
  13. 97、爬虫框架scrapy
  14. git常用命令速查
  15. vue项目中的相关插件
  16. Mysql8 查询事务隔离级别
  17. yum 安装Mysql
  18. volatile的实现原理与应用
  19. 【13】享元模式(FlyWeight Pattern)
  20. MySql处理函数

热门文章

  1. Openshift 4.4 静态 IP 离线安装系列:初始安装
  2. Jmeter(十一) - 从入门到精通 - JMeter逻辑控制器 - 下篇(详解教程)
  3. 基于SSM框架的新生报到可视化系统
  4. java小项目——抽奖系统
  5. skywalking面板功能介绍2
  6. nova api报错network问题
  7. linux下将多个ts文件合并为一个MP4文件
  8. 报错 500 - Request processing failed; nested exception is com.alibaba.dubbo.rpc.RpcException的解决放案
  9. 浅谈MySQL数据库基本操作
  10. 《算法笔记》6.6小节 问题 A: 任务调度