lg2294 发表于 2018-11-26 | 阅读数 次 链接:lg2294 题解 显然可以差分约束做,区间上的约束问题,显然可以转换成前缀和的点上的约束问题,注意u->v建边为c时要建一条v->u边权为-c的边 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e5+7;const int inf=0x3f3f3f3f;int T,n,m,cnt;int head[N],to[N],nxt[N],inq[N],w[N],dis[N],tot[N];queue<int>q;inline void adde(int a,int b,int c){ to[++cnt]=b; w[cnt]=c; nxt[cnt]=head[a]; head[a]=cnt;}int spfa(int u){ while(!q.empty())q.pop(); q.push(u); inq[u]=1;dis[u]=0; while(!q.empty()){ int k=q.front();q.pop(); inq[k]--; for(int i=head[k];i;i=nxt[i])if(dis[to[i]]>dis[k]+w[i]){ dis[to[i]]=dis[k]+w[i]; tot[to[i]]++; if(tot[to[i]]>=n)return 0; if(!inq[to[i]]){ q.push(to[i]); inq[to[i]]++; } } } return 1;}int main(){ scanf("%d",&T); while(T--){ cnt=0; memset(dis,0x3f,sizeof dis); memset(inq,0,sizeof inq); memset(head,0,sizeof head); memset(tot,0,sizeof tot); scanf("%d%d",&n,&m); rep(i,1,m){ int a,b,c; scanf("%d%d%d",&a,&b,&c); adde(a-1,b,c);adde(b,a-1,-c); } int ans=0; rep(i,0,n)if(!tot[i]&&!spfa(i)){ans=1;break;} puts(ans?"false":"true"); } return 0;}