bzoj3436小K的农场
2024-09-05 20:38:19
题意:
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
最新文章
- v$session中server为none与shared值解析
- 自定义RatingBar的一个问题(只显示显示一个星星)
- 【CodeVS2800】 送外卖 最短路+状压DP
- 20151011 C# 第一篇 运算符
- Biee 迁移和刷新GUIDs
- DateUtils
- Codeforces 733C:Epidemic in Monstropolis(暴力贪心)
- CollectionsAPI
- [Spring] IOC - study
- 洛谷P1204 [USACO1.2]挤牛奶Milking Cows
- Arrays类与Array类探究
- 6.python内置函数
- 97、爬虫框架scrapy
- git常用命令速查
- vue项目中的相关插件
- Mysql8 查询事务隔离级别
- yum 安装Mysql
- volatile的实现原理与应用
- 【13】享元模式(FlyWeight Pattern)
- MySql处理函数
热门文章
- Openshift 4.4 静态 IP 离线安装系列:初始安装
- Jmeter(十一) - 从入门到精通 - JMeter逻辑控制器 - 下篇(详解教程)
- 基于SSM框架的新生报到可视化系统
- java小项目——抽奖系统
- skywalking面板功能介绍2
- nova api报错network问题
- linux下将多个ts文件合并为一个MP4文件
- 报错 500 - Request processing failed; nested exception is com.alibaba.dubbo.rpc.RpcException的解决放案
- 浅谈MySQL数据库基本操作
- 《算法笔记》6.6小节 问题 A: 任务调度