这个题可以用并查集做，这里是之前一个图论学傻了的蒟蒻的差分约束做法。。
我们考虑题面中的条件，
若ｓ到ｔ的为ｗ，就相当于sum[t]-sum[s-1]=w。
那么就是sum[t]-sum[s-1]>=w,sum[t]-sum[s-1]<=w,
同时化成最短路松弛形式得到：sumt[s-1]+w<=sum[t],sum[t]+(-w)<=sum[s-1]。
那么容易发现，只需要从ｓ－１向ｔ连一条ｗ的边，再从ｔ向ｓ－１连一条－ｗ的边就好了。
最后就是直接ｓｐｆａ判环就好了。
#include <bits/stdc++.h> using namespace std; inline int gi () { int x=0,w=0;char ch=0; while(!(ch>=‘0‘&&ch<=‘9‘)) { if(ch==‘-‘) w=1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } const int N=110; const int M=2010; bool inq[N]; queue <int> q; int w,n,m,s,end,Sum,tot,flag,cnt[N],vis[N],head[N],val[N]; struct edge { int next, now, ver; }e[M]; void make (int from, int to, int v) { e[++tot].next=head[from]; head[from]=tot; e[tot].now=to; e[tot].ver=v; } bool SPFA (int k) { memset (val,-0x3f3f3f3f,sizeof (val)); memset (cnt,0,sizeof (cnt)); memset (inq,0,sizeof (inq)); q.push (k); inq[k]=1, val[k]=0; int x,y,i; while (!q.empty ()) { x=q.front (); q.pop (), inq[x]=0, vis[x]=1; for (i=head[x];i;i=e[i].next) { y=e[i].now; if (val[x]+e[i].ver>val[y]) { if (++cnt[y]>=n) return 0; val[y]=val[x]+e[i].ver; if (!inq[y]) q.push (y), inq[y]=1; } } } return 1; } int main () { w=gi (); while (w--) { n=gi (), m=gi (); tot=0; flag=0; memset (head,0,sizeof (head)); memset (vis,0,sizeof (vis)); memset (&e,0,sizeof (e)); for (int i=1;i<=m;++i) { s=gi (), end=gi (), Sum=gi (); make (s-1, end, Sum), make (end, s-1, -Sum); } for (int i=0;i<=n;++i) { if (vis[i]) continue; if (!SPFA (i)) { flag=1; break; } } flag?printf ("false\n"):printf ("true\n"); } return 0; }
原文：https://www.cnblogs.com/Bhllx/p/9928995.html