首页 > 代码库 > BZOJ3436: 小K的农场
BZOJ3436: 小K的农场
3436: 小K的农场
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 185 Solved: 103
[Submit][Status]
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
33
312
1131
2232
312
1131
2232
Sample Output
Yes
样例解释
三个农场种植的数量可以为(2,2,1)。
对于100%的数据,1<=n,m,a,b,c<=10000
HINT
Source
Kpmcup#0 By Greens
题解:
云神居然会出这种题。。。
裸spfa判负环。
代码:
View Code
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 1500014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 struct edgs{int go,next,w;}e[maxn];32 int n,m,tot,head[maxn],d[maxn];33 bool v[maxn],flag;34 void insert(int x,int y,int z)35 {36 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z;37 }38 void spfa(int x)39 {40 if(v[x]){flag=1;return;}41 v[x]=1;42 for(int i=head[x],y;i;i=e[i].next)43 if(d[x]+e[i].w<d[y=e[i].go])44 {45 d[y]=d[x]+e[i].w;46 spfa(y);47 if(flag)break;48 }49 v[x]=0;50 }51 int main()52 {53 freopen("input.txt","r",stdin);54 freopen("output.txt","w",stdout);55 n=read();m=read();56 for1(i,m)57 {58 int ch=read(),x=read(),y=read();59 if(ch==3)insert(x,y,0);60 else 61 {62 int z=read();63 if(ch==1)insert(x,y,-z);else insert(y,x,z);64 }65 }66 for1(i,n)67 {68 spfa(i);69 if(flag)break;70 }71 if(!flag)cout<<"Yes"<<endl;else cout<<"No"<<endl;72 return 0;73 }
BZOJ3436: 小K的农场
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。