文档章节

小K的农场 差分约束

Loi_DL
 Loi_DL
发布于 2016/11/03 07:41
字数 611
阅读 5
收藏 0

Description
 背景

    小K是个特么喜欢玩MC的孩纸。。。

 描述

    小K在MC里面建立很多很多的农场,总共n个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m个),以下列三种形式描述:农场a比农场b至少多种植了c个单位的作物,农场a比农场b至多多种植了c个单位的作物,农场a与农场b种植的作物数一样多。但是,由于小K的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。输入格式

Input

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

    接下来m行:

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

    如果每行第一个数是3,接下来有两个整数a,b,表示农场a种植的数量与b一样多输出格式

Output

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

Sample Input

3 3 3 1 2 1 1 3 1 2 2 3 2
#include <iostream> 
#include <cstring> 
#include <algorithm> 
#include <cstdio> 
#define inf 0x7fffffff 
#define maxn 23333 
using namespace std; 
int next[maxn],head[maxn],to[maxn],len[maxn]; 
int dis[maxn]; int n,m,num,flag=0; 
bool vis[maxn]; 
void build (int x,int y,int z)
{ 
	num++; 	
	to[num]=y; 
	len[num]=z; 
	next[num]=head[x]; 
	head[x]=num; 
} 
void spfa(int x)// 递归spfa 速度有点慢 这个题还是能水一水的 
{ 
	vis[x]=1; 
	for(int p=head[x];p;p=next[p]) 
	if(dis[to[p]]>dis[x]+len[p]) 
	{
	 	if(vis[to[p]]) 
		{ 
			flag=1; 		
			break; 
		} 
		dis[to[p]]=dis[x]+len[p]; 
		spfa(to[p]); 
	} 
		vis[x]=0; 
}	 
int main() 
{ 
	int n,m; 
	scanf("%d%d",&n,&m); 
	for(int i=1;i<=m;i++) 
	{ 	
		int op,x,y,z; 
		scanf("%d%d%d",&op,&x,&y); 
		if(op==1) 
		{ 
			scanf("%d",&z); 
			build(x,y,-z);
		}
		if(op==2) 
		{ 
			scanf("%d",&z); 
			build(y,x,z); 
		} 
		if(op==3) 	
		build(x,y,0); 
	} 
	for(int i=1;i<=n;i++) 
	{ 	
		dis[i]=0; 
		spfa(i); 	
	}	 
	if(flag==1) 
		printf("No\n"); 
	else 
		printf("Yes\n"); 
	return 0; 
}

 

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
差分约束算法总结

差分约束系统 一、概念 如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。 二、引例 给定n个变量和m个不等式,每个不等式的...

my_sunshine26
2017/06/03
0
0
UC伯克利 ICLR 论文:论如何教强化学习模型骑自行车去金门大桥?

雷锋网 AI 科技评论按:本文的作者是来自加州大学伯克利分校人工智能实验室(BAIR)的博士生 Vitchyr Pong,他的主研方向为深度强化学习。在本篇博客中作者介绍了自己发表于正在进行的 ICLR...

隔壁王大喵
2018/05/03
0
0
POJ 3159 Candies 【差分约束】

传送门 题意: 给定n个限制关系u v w表示u认为v的糖果数量最多比它多w个. 问在满足这些的条件下, 1与n的糖果数量最大的差是多少. 思路: 知道差分约束的很容易可以判断出这个是差分约束, 我们用...

Anxdada
2018/02/13
0
0
ARIMA时间序列分析-----Python实例(一周销售营业额预测)

以ARIMA模型为例介绍时间序列算法在python中是如何实现的,一下是应用Python语言建模步骤: -- coding: utf-8 -- “”” Created on Mon Apr 2 16:45:36 2018 @author: houy “”“ arima模型...

xingchenhy
2018/04/12
0
0
Python 用于金融数据分析第9课 Part 2-----时间序列分析模型ARIMA实现

ARIMA模型实现预测的流程 流程图 一、导入数据 我们先在终端看一下牛奶产量这个文件的前几行再决定要怎么样读取这个csv文件。 文件概览 我们可以看到有两列,第一列是时间,第二列是产量,因...

九日照林
2018/03/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ant 中的fileset include等拷贝

拷贝一个目录到指定目录下 例:<copy todir="${basedir}/new"> <fileset dir="${basedir}/old"> <include name="appgen" /> <include name="appgen/" /> <include name=appgen/**" /> <incl......

shzwork
23分钟前
2
0
react-jianshu项目的创建

创建项目 1、github上创建仓库react-jianshu 2、将项目克隆到本地git clone git@github.com:startjcu/react-jianshu.git 3、在当前目录(项目目录的上级目录)下执行create-react-app react-...

星闪海洋
32分钟前
2
0
OSChina 周二乱弹 —— 小哥哥,你可以教我写代码吗

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @nnnm: 生活大爆炸,结束了,这部陪伴了漫长时间的情景喜剧,最终是以诺贝尔奖和大团圆收尾的。虽然,不算精彩,但也是温馨。而少年谢尔顿的...

小小编辑
今天
419
11
typescript 接口 函数类型 可索引类型

函数类型 可索引类型 数字索引签名 字符串索引签名 数字索引签名返回值 必须是 字符串索引签名返回值的子集 只读索引签名

lilugirl
今天
4
0
Oracle SQL语法实例合集

如需转载请注明出处https://my.oschina.net/feistel/blog/3052024 目的:迅速激活Oracle SQL 参考:《Oracle从入门到精通》 ------------------------------------------------------------......

LoSingSang
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部