BZOJ3436 小K的农场
2024-08-27 13:17:21
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一样。1<=n,m,a,b,c<=10000
Output
如果存在某种情况与小K的记忆吻合,输出”Yes”,否则输出”No”
Sample Input
3 3
3 1 2
1 1 3 1
2 2 3 2
3 1 2
1 1 3 1
2 2 3 2
Sample Output
Yes
样例解释
三个农场种植的数量可以为(2,2,1)
样例解释
三个农场种植的数量可以为(2,2,1)
HINT
Source
正解:差分约束系统
解题报告:
这道题就是一道差分约束系统裸题。
好久没做差分约束系统的题我都快忘了怎么连边了...首先如果x-y<=z,那么显然y的值到x的值必须要把差控制在z以内,所以应该是y向x连边,边权为z;如果是x-y>=z,那么,显然是转成y-x<=-z,所以x向y连一条-z的边(一般都习惯以小于号为主体)。所以我们只要找负权环就可以了。
相等的时候并不用考虑,直接连一条边权为0的边即可,一条两条随意。
当然,找负权环,dfs版SPFA肯定要优秀一些。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
int n,m,ecnt,top;
int first[MAXN],to[MAXM],next[MAXM],w[MAXM],dis[MAXN];
int stack[MAXN],cnt[MAXN];
bool in[MAXN]; inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
}
inline void link(int x,int y,int z){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z; }
inline bool SPFA(){
for(int i=;i<=n;i++) dis[i]=,stack[++top]=i,in[i]=;
int u;
while(top>) {
u=stack[top]; top--; in[u]=;
for(int i=first[u];i;i=next[i]) {
int v=to[i];
if(dis[v]>dis[u]+w[i]) {
dis[v]=dis[u]+w[i];
if(!in[v]) { in[v]=; stack[++top]=v; cnt[v]++; if(cnt[v]>=n) return false;}
}
}
}
return true;
} inline void work(){
n=getint(); m=getint(); int x,y,z,ljh;
for(int i=;i<=m;i++) {
ljh=getint(); x=getint(); y=getint();
if(ljh==) z=getint(),link(x,y,-z);
else if(ljh==) z=getint(),link(y,x,z);
else link(x,y,);
}
if(SPFA()) printf("Yes"); else printf("No");
} int main()
{
work();
return ;
}
最新文章
- phpmyadmin #1045 - Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: NO)
- Mac:文件夹树型展示 tree
- jquery选择伪元素属性的方法
- Java项目下jar包的放置
- (转)MFC中获得各个类的指针/句柄 ID的总结
- PeopleSoft Related Language Records
- Caused by: 元素类型为 ";package"; 的内容必须匹配 ";(result-types?,interceptors?,default-interceptor-ref?,default-action-ref?,default-class-ref?,global-results?,global-exception-mappings?,action*)";
- RDoc
- TypeScript学习指南第二章--接口(Interface)
- Event Sourcing - ENode(一)
- 扩展SQLite使其能从apk文件中读取db
- layer使用总结
- python3 字符编码与转码的理解
- SQLServer事务在C#当中的应用
- Angular4.x学习日志
- [Swift]LeetCode254.因子组合 $ Factor Combinations
- C#版的 Escape() 和 Unescape()
- Codeforces Round #536 (Div. 2) E dp + set
- BZOJ2351[BeiJing2011]Matrix——二维hash
- Ext.NET Ext.JS 常用代码片段摘录