差分约束之狡猾的商人

题目

狡猾的商人

思路

用spfa求解，查询当前是否合法，正向加正边，反向加反边。记得判负环。

#include<bits/stdc++.h>
using namespace std;
const int maxm=500+10,maxn=4000+10;
int head[maxn],ver[maxm],edge[maxm],Next[maxm],tot;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
int read(){
    char c=getchar();
    int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
int vis[maxn],dis[maxn];
int cnt[maxn];
bool flag=0;int n;
void spfa(int s){
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    dis[s]=0,vis[s]=1;
    q.push(s);cnt[s]++;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=Next[i]){
            int v=ver[i];
            if(dis[v]>dis[u]+edge[i]){
                dis[v]=dis[u]+edge[i];
                if(!vis[v]){
                    cnt[v]++;
                    q.push(v);
                    vis[v]=1;
                    if(cnt[v]>n+1){
                        flag=1;
                        return;
                    }
                }
            }
        }

    }
}

int main(){
    int t;t=read();
    for(int tt=1;tt<=t;tt++){
        tot=0;
        memset(head,0,sizeof(head));
        int m;
        n=read(),m=read();
        for(int i=1;i<=m;i++){
            ver[i]=0,edge[i]=0,Next[i]=0;   
        }
        n++;flag=0;
        for(int i=1;i<=m;i++){
            int l,r,w;
            l=read(),r=read(),w=read();
            r++;
            spfa(l);
            if(flag==1){
                printf("false\n");
                break;
            }
            if(dis[r]>=1061109567){
                add(l,r,w);
                add(r,l,-w);
            }
            else{
                if(dis[r]!=w){
                    printf("false\n");
                    flag=1;
                    break;          
                }
            }
        }
        if(!flag)printf("true\n");
    }
}