[BZOJ1202]狡猾的商人

 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 }