@zzzc18 2017-11-09T16:51:36.000000Z 字数 965 阅读 921

# SPFA判负环

模板库

#include<bitset>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN = 200000+9;const int MAXM = 200000+9;struct E{    int next,to;    int val;}edge[MAXM<<1];int head[MAXN],edge_num;int n,m;bool pd;bitset<MAXN> vis;int dis[MAXN];void addedge(int x,int y,int v){    edge[++edge_num].next=head[x];    edge[edge_num].to=y;    edge[edge_num].val=v;    head[x]=edge_num;}void SPFA(int x){    if(pd)return;    vis[x]=1;    for(int i=head[x];i;i=edge[i].next){        if(pd)return;        if(dis[x]+edge[i].val<dis[edge[i].to]){            dis[edge[i].to]=dis[x]+edge[i].val;            if(vis[edge[i].to]){                pd=1;                return;            }            SPFA(edge[i].to);        }    }    vis[x]=0;}void solve(){    for(int i=1;i<=n;i++){        SPFA(i);        if(pd){puts("YE5");return;}    }    puts("N0");}int main(){    int kase;    scanf("%d",&kase);    while(kase--){        memset(head,0,sizeof(head));        vis.reset();        memset(dis,0,sizeof(dis));        edge_num=0;        pd=0;        scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++){            int a,b,c;            scanf("%d%d%d",&a,&b,&c);            addedge(a,b,c);            if(c>=0)addedge(b,a,c);        }        solve();    }    return 0;}

• 私有
• 公开
• 删除