思路是差分约束+dfs版SPFA。
首先来思考差分约束的过程，将题目给出的式子进行转化：
- 农场a比农场b至少多种植了c个单位的作物，
SPFA我们考虑跑最短路，那么要让SPFA中满足的式子就是if(d[b]>d[a]-c)d[b]=d[a]-c，即让b<=a-c。
所以建一条a->b权值为-c的边，使d[b]始终满足<=d[a]-c。
- 农场a比农场b至多多种植了c个单位的作物，
同理，建一条b->a，权值为c的边。
- 农场a与农场b种植的作物数一样多。
建一条a，b间的双向边，权值为0。即建两条单向权值为0的边。
最后处理完所有条件，考虑存在整张图不连通的情况——这时候我们需要一个点能把整张图串起来，又不会影响到结果，即“超级源点”0点。
由0点向每个点建一条权值为0的边。
然后就是SPFA松弛，判负环的过程。这里用dfs版的SPFA不然会T。
代码如下：
#include#include #include #include using namespace std;int n,m,d[10001],vis[10001],cnt[10001],flag;int ver[50001],Next[50001],edge[50001],head[10001],tot;queue q; void add(int a,int b,int c){ ver[++tot]=b; Next[tot]=head[a]; edge[tot]=c; head[a]=tot;}int spfa(int x){ vis[x]=1; for(int i=head[x];i;i=Next[i]){ int v=ver[i],z=edge[i]; if(d[v]>d[x]+z){ d[v]=d[x]+z; if(vis[v])return 0; if(!spfa(v))return 0; } } vis[x]=0; return 1;}int main(){ scanf("%d%d",&n,&m); for(int i=1,k,a,b,c;i<=m;i++){ scanf("%d",&k); if(k==1){ scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } if(k==2){ scanf("%d%d%d",&a,&b,&c); add(b,a,c); } if(k==3){ scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } for(int i=1;i<=n;i++)add(0,i,0); memset(d,0x3f,sizeof(d)); d[0]=0; if(!spfa(0))printf("No"); else printf("Yes"); return 0; }