题解——洛谷P2294 [HNOI2005]狡猾的商人（差分约束）

裸的差分约束

dfs判断负环，如果有负环就false，否则就是true

注意有多组数据，数组要清空

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

#include <iostream>

using namespace std;

const int MAXN = ;

const int MAXM = ;

int cnt=,u[MAXM],v[MAXM],w[MAXM],first[MAXN],next[MAXM];

int vis[MAXN];

int inq[MAXN],dis[MAXN],f[MAXN];

int n,m;

void addedge(int ux,int vx,int wx){

    ++cnt;

    u[cnt]=ux;

    v[cnt]=vx;

    w[cnt]=wx;

    next[cnt]=first[ux];

    first[ux]=cnt;

}

bool flag=false;

void spfa(int ux){

    vis[ux]=;

    for(int i=first[ux];i;i=next[i]){

        if(dis[ux]+w[i]<dis[v[i]]){

            if(vis[v[i]]){

                flag=true;

                return;

            }

            dis[v[i]]=dis[ux]+w[i];

            spfa(v[i]);

        }

    }

    vis[ux]=;

    return;

}

/*bool spfa(int s,int t){

    queue<int> q;

    q.push(s);

    dis[s]=0;

    inq[s]=1;

    vis[s]=1;

    f[s]=1;

    while(!q.empty()){

        int u=q.front();

        q.pop();

        vis[u]=0;

        f[u]=1;

        for(int i=first[u];i;i=next[i]){

            if(w[i]+dis[u]<dis[v[i]]){

                dis[v[i]]=w[i]+dis[u];

                if(!vis[v[i]]){

                    vis[v[i]]=1;

                    inq[v[i]]++;

                    q.push(v[i]);

                    if(inq[v[i]]>=n)

                        return false;

                }

            }

        }

    }

    return true;

}*/

int main(){

    int T,sx,tx,vx;

    cin>>T;

    for(int pp=;pp<=T;pp++){

    flag=false;

    cin>>n>>m;

    cnt=;

    memset(dis,0x3f,sizeof(dis));

    memset(first,,sizeof(first));

    memset(vis,,sizeof(vis));

    memset(f,,sizeof(f));

    for(int i=;i<=m;i++){

        cin>>sx>>tx>>vx;

        addedge(sx-,tx,vx);

        addedge(tx,sx-,-vx);

    }

    for(int i=;i<=n;i++){

        if(!f[i]){

            dis[i]=;

            spfa(i);

            if(flag){

                printf("false\n");

                break;

            }

        }

    }

    if(!flag){

    printf("true\n");

    }

}

    return ;

}