博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
小K的农场
阅读量:5142 次
发布时间:2019-06-13

本文共 1596 字,大约阅读时间需要 5 分钟。

小K的农场

题目描述

小K在MC里面建立很多很多的农场,总共n个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m个),以下列三种形式描述:

  • 农场a比农场b至少多种植了c个单位的作物,
  • 农场a比农场b至多多种植了c个单位的作物,
  • 农场a与农场b种植的作物数一样多。

但是,由于小K的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式

输入格式:

第一行包括两个整数 n 和 m,分别表示农场数目和小 K 记忆中的信息数目。

接下来 m 行:

如果每行的第一个数是 1,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至少多种植了 c 个单位的作物。

如果每行的第一个数是 2,接下来有 3 个整数 a,b,c,表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3,接下来有 2 个整数 a,b,表示农场 a 种植的的数量和 b 一样多。

输出格式:

如果存在某种情况与小 K 的记忆吻合,输出“Yes”,否则输出“No”。

输入输出样例

输入样例#1:

3 3

3 1 2
1 1 3 1
2 2 3 2

输出样例#1:

Yes

说明

对于 100% 的数据保证:\(1 ≤ n,m,a,b,c ≤ 10000.\)

题解

看到题目中的三个条件,应该可以看出这是一道差分约束题了

首先抛开题目,如果一个式子满足

\[dis[j]>=dis[i]+w[i,j]\]
应该可以想到最长路的三角不等式

对于一条边(u,v,w),我们认为v点的值需要至少比u点大w

所以对于1条件,可以简化为\(dis[a]>=dis[b]+c\),我们建一条由b到a的边,边权为c

对于2条件,\(dis[a]<=dis[b]+c\),转化为\(dis[b]>=dis[a]-c\),建一条由a到b的边,边权为-c

对于3条件,\(dis[a]=dis[b]\),建双向边(a,b),边权为0

其次,为了保证图联通,我们吧每个节点向0点建一条边权为0的边

所以数组就要开3倍!!!!!

然后跑最短路就可以了,SPFA判环,最长路判正环,最短路判负环,没什么要注意的了

Code

#include
#define rg register#define Min(a,b) (a)<(b)?(a):(b)using namespace std;const int N=10010,M=10010;const int inf=2e9;int in(int &ans){ ans=0; int f=1; char i=getchar(); while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();} while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar(); ans*=f;}bool flag;int cnt,n,m,T;int to[M<<2],nex[M<<2],w[M<<2],head[N],dis[N],vis[N];inline void add(int a,int b,int c){ to[++cnt]=b,nex[cnt]=head[a]; w[cnt]=c,head[a]=cnt;}void SPFA(int u){ vis[u]=1; for(int i=head[u];i;i=nex[i]) { if(dis[to[i]]

博主蒟蒻,随意转载.但必须附上原文链接

转载于:https://www.cnblogs.com/real-l/p/9547725.html

你可能感兴趣的文章
ionic2+ 基础
查看>>
MyBaits动态sql语句
查看>>
用户空间与内核空间,进程上下文与中断上下文[总结]
查看>>
JAVA开发环境搭建
查看>>
Data truncation: Out of range value for column 'Quality' at row 1
查看>>
ad logon hour
查看>>
Linux内核态、用户态简介与IntelCPU特权级别--Ring0-3
查看>>
第23月第24天 git命令 .git-credentials git rm --cached git stash clear
查看>>
java SE :标准输入/输出
查看>>
[ JAVA编程 ] double类型计算精度丢失问题及解决方法
查看>>
好玩的-记最近玩的几个经典ipad ios游戏
查看>>
tmux的简单快捷键
查看>>
[Swift]LeetCode922.按奇偶排序数组 II | Sort Array By Parity II
查看>>
Vue_(组件通讯)子组件向父组件传值
查看>>
移动开发平台-应用之星app制作教程
查看>>
DataGridView的行的字体颜色变化
查看>>
[Serializable]的应用--注册码的生成,加密和验证
查看>>
Android-多线程AsyncTask
查看>>
LeetCode【709. 转换成小写字母】
查看>>
如果没有按照正常的先装iis后装.net的顺序,可以使用此命令重新注册一下:
查看>>