P3385 【模板】负环

题目链接 https://www.luogu.com.cn/problem/P3385

SPFA还没学欸，用的Bellman-Ford。

用链式前向星这样的了。。。

然后干脆用数组了。。。

注意第45行的特判，因为存在某点不连通的情况。（差点没要我命...）

放AC代码

 1 #include
 2 using namespace std;
 3 const int N=2e6 + 1000;
 4 int t,n,m;
 5 int cnt;
 6 long long dis[N];
 7 bool vis[N];
 8 
 9 struct Edge
10 {
11     int u,v,w;
12 } edge[N];
13 
14 void add(int u,int v,int w)
15 {
16     edge[++cnt]= {u,v,w};
17 }
18 
19 void addd(int u,int v,int w)
20 {
21     if(w<0) add(u,v,w);
22     if(w>=0) add(u,v,w),add(v,u,w);
23 }
24 
25 bool bellman_ford()
26 {
27     for(int i=1; i<=n; i++)
28     {
29         dis[i]=INT_MAX;
30     }
31     dis[1]=0;
32 
33     for(int i=1; i)
34     {
35         for(int j=1; j<=cnt; j++)
36         {
37             if(dis[edge[j].u]!=INT_MAX && dis[edge[j].v]>dis[edge[j].u]+edge[j].w)
38                 dis[edge[j].v]=dis[edge[j].u]+edge[j].w;
39         }
40     }
41 
42     bool flag=1;//标记有无负环
43     for(int i=1; i<=cnt; i++)
44     {
45         if(dis[edge[i].u]==INT_MAX || dis[edge[i].v]==INT_MAX)//存在不连通的节点
46             continue;
47         if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)//松弛是否成功
48         {
49             flag=0;//成功则有负环
50             break;
51         }
52     }
53     return flag;
54 }
55 
56 int main()
57 {
58     cin>>t;
59     while(t--)
60     {
61         cin>>n>>m;
62         cnt=0;
63         for(int i=1; i<=m; i++)
64         {
65             int u,v,w;
66             cin>>u>>v>>w;
67             addd(u,v,w);
68         }
69         if(bellman_ford())
70             cout<<"NO"<<endl;
71         else
72             cout<<"YES"<<endl;
73     }
74     return 0;
75 }

um....顺便存一下错误的链式前向星

 1 #include
 2 using namespace std;
 3 int t,n,m;
 4 int cnt;
 5 int head[3010];
 6 long long dis[3010];
 7 bool vis[3010];
 8 
 9 struct Edge
10 {
11     int u,v,w;
12     int next;
13 } edge[3010];
14 
15 void add(int u,int v,int w)
16 {
17     edge[++cnt].v=v;
18     edge[cnt].w=w;
19     edge[cnt].next=head[u];
20     head[u]=cnt;
21 }
22 
23 void addd(int u,int v,int w)
24 {
25     if(w<0) add(u,v,w);
26     if(w>=0) add(u,v,w),add(v,u,w);
27 }
28 
29 bool bellman_ford()
30 {
31     for(int i=1; i<=n; i++)
32     {
33         dis[i]=INT_MAX;
34     }
35 
36     int cur=1;
37     dis[cur]=0;
38 
39     while(!vis[cur])
40     {
41         vis[cur]=true;
42         for(int i=head[cur]; i!=0; i=edge[i].next)
43         {
44             if(!vis[edge[i].v] && dis[edge[i].v]>dis[cur]+edge[i].w)
45                 dis[edge[i].v]=dis[cur]+edge[i].w;
46         }
47     }
48 
49     bool flag=1;
50     for(int i=head[cur]; i!=0; i=edge[i].next)
51     {
52         if(!vis[edge[i].v] && dis[edge[i].v]>dis[cur]+edge[i].w)
53         {
54             flag=0;
55             break;
56         }
57     }
58     return flag;
59 }
60 
61 int main()
62 {
63     cin>>t;
64     while(t--)
65     {
66         cin>>n>>m;
67         cnt=0;
68         for(int i=1; i<=m; i++)
69         {
70             int u,v,w;
71             cin>>u>>v>>w;
72             addd(u,v,w);
73         }
74         if(bellman_ford())
75             cout<<"NO"<<endl;
76         else
77             cout<<"YES"<<endl;
78     }
79     return 0;
80 }