知识点：差分约束、

难点：找到正确的不等关系然后建图

关于建图：

　　一段时间内的收入及前缀和，l~r天的收入用前缀和表达即sum[r]-sum[l-1];

　　对于每一个账本，如果它是假的，可能会出现这种情况：

sum[1,2]=1,sum[2,3]=1,sum[1,3]=1

　　显然：第一天第二天第三天收入为2，与sum[1,3]=1矛盾，我们要做的就是找到这个矛盾的地方

　　　　然后有一个显然的建图方法：sum[v]−sum[u−1]=c，sum[u-1]-sum[v]=−c。

　　然后跑SPFA套模板即可

 

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 inline int read(){
 8     char chr=getchar();    int f=1,ans=0;
 9     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
11     return ans*f;
12 }const int M=200005;queue<int> q;
13 int head[M],ver[M],nxt[M],val[M],tot[M],T_T,T,n,m,x,y,z,ff,dis[M],vis[M];
14 inline void add(int x,int y,int z){ver[++T_T]=y;nxt[T_T]=head[x];val[T_T]=z;head[x]=T_T;}
15 #define y ver[i]
16 inline bool spfa(int x){memset(dis,0xcf,sizeof(dis));memset(vis,0,sizeof(vis));
17     while(!q.empty()) q.pop();
18     q.push(x),dis[x]=0;vis[x]=1;
19     while(!q.empty()){
20         int fx=q.front();q.pop();vis[fx]=0;tot[fx]++;
21         if(tot[fx]==n) return 0;
22         for(int i=head[fx];i;i=nxt[i])
23             if(dis[fx]+val[i]>dis[y]){
24                 dis[y]=dis[fx]+val[i];
25                 if(!vis[y]) q.push(y),vis[y]=1;
26             }
27     }return 1;}
28 #undef y
29 int main(){
30     T=read();
31     while(T--){n=read(),m=read();ff=0;T_T=0;
32         memset(vis,0,sizeof(vis));memset(head,0,sizeof(head));memset(tot,0,sizeof(tot));memset(nxt,0,sizeof(nxt));
33         for(int i=1;i<=m;i++)x=read(),y=read(),z=read(),add(x-1,y,z),add(y,x-1,-z);
34         for(int i=0;i<=n;i++)    if(!tot[i])if(!spfa(i)){ff=1;break;}
35         if(ff) puts("false");
36         else puts("true");
37     }return 0;
38 }