首页 > 代码库 > BZOJ3436: 小K的农场

BZOJ3436: 小K的农场

2024-08-02 07:12:38   219人阅读

3436: 小K的农场

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 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

Sample Output


Yes

样例解释

三个农场种植的数量可以为（2,2,1）。


对于100%的数据，1<=n,m,a,b,c<=10000


HINT

 

Source

Kpmcup#0 By Greens

题解：
云神居然会出这种题。。。
裸spfa判负环。
代码：
 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 }
View Code

 

BZOJ3436: 小K的农场


联系
我们