[文章目录]
Description
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
差分约束。
如果a比b至多多c个单位，那么只需要通过a带着b提高就好了，由a向b连一条-c的边。
论判正权环的正确打开方式？？？
1.记录入队次数，超过n就return 时间：9184ms
2.记录优化的节点路径长度。if(dis[y]<dis[x]+w) len[y]=len[x]+1; 超过n就return 时间4682ms
3.学习一个QwQ @EdwardFrod :一边判定方法1，一边判断进行优化的次数。如果超过一个定值，那么就return 时间92ms（具体是否正确我也不知道。。。）
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,sum;
int head[10100],to[51100],nxt[51100],f[51100],cnt;
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
f[cnt]=z;
}
int len[11000],dis[11000];
bool inq[11000];
queue<int>q;
bool spfa()
{
memset(dis,0xef,sizeof dis);
dis[s]=0; q.push(s); inq[s]=1; len[s]=1;
int x,i;
while(!q.empty())
{
x=q.front(); q.pop(); inq[x]=0;
for(i=head[x];i;i=nxt[i])
if(dis[to[i]]<dis[x]+f[i])
{
dis[to[i]]=dis[x]+f[i];
if(!inq[to[i]]){
inq[to[i]]=1; q.push(to[i]); len[to[i]]++; sum++;
if(len[to[i]]>=n||sum>=5*n) return false;
}
}
}
return true;
}
int main()
{
scanf("%d%d",&n,&m); int sw,x,y,z;
for(int i=n;i;--i) add(s,i,0);
while(m--)
{
scanf("%d",&sw);
if(sw==1)
{
scanf("%d%d%d",&x,&y,&z);
add(y,x,z);
if(x==y)
{
puts("No");
return 0;
}
}
else if(sw==2)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,-z);
}
else
{
scanf("%d%d",&x,&y);
add(x,y,0); add(y,x,0);
}
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}