负环

luogu上的一道题

这道题可以用DFS—spfa

思路就是在开始搜索的时候标记一下开始的节点

然后递归spfa

如果搜着搜着发现某个节点已经被访问过，即存在负环

放代码

 1 #include<cstdlib>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cctype>
 5 int read(){
 6     int num=0,f=1;
 7     char ch=getchar();
 8     while(!isdigit(ch)){
 9         if(ch=='-')    f=-1;
10         ch=getchar();
11     }
12     while(isdigit(ch)){
13         num=num*10+ch-'0';
14         ch=getchar();
15     }
16     return num*f;
17 }
18 
19 struct Edge{
20     int to,dis,next;
21 }edge[1000000];
22 int head[500000],num=0;
23 int dis[500000];
24 
25 
26 int vis[500000];
27 bool flag=0;
28 
29 void add(int from,int to,int dis){
30     edge[++num].next=head[from];
31     edge[num].to=to;
32     edge[num].dis=dis;
33     head[from]=num;
34 }
35 
36 void spfa(int x){
37     if(flag)return;
38     vis[x]=1;
39     for(int i=head[x];i;i=edge[i].next){
40         int to=edge[i].to;
41         if(dis[to]>dis[x]+edge[i].dis){
42             if(vis[to]||flag){
43                 flag=1;
44                 return;
45             }
46             dis[to]=dis[x]+edge[i].dis;
47             spfa(to);
48         }
49     }
50     vis[x]=0;
51 }
52 
53 int main(){
54     memset(dis,127/3,sizeof(dis));
55     int _=read();
56     while(_--){
57         int n=read(),m=read();
58         int a,b,w;
59         for(int i=1;i<=m;++i){
60             a=read(),b=read(),w=read();
61             add(a,b,w);
62             if(w>0)    add(b,a,w);
63         }
64         for(int i=1;i<=n;++i){
65             spfa(i);
66             if(flag)    break;
67         }
68         if(flag){
69             printf("YE5
");
70         }
71         else printf("N0
");
72         num=0;
73         memset(edge,0,sizeof(edge));
74         memset(head,0,sizeof(head));
75         memset(dis,127/3,sizeof(dis));
76         memset(vis,0,sizeof(vis));
77         flag=0;
78     }
79     return 0;
80 }