洛谷P3385负环 题解

洛谷 P3385 【模板】负环

SPFA死了,但是它还活着!

给定一张图,判断是否有负权环!

SPFA走起!

当一个点入队次数超过n次时候,那么这张图上存在负权环。

开个数组统计一下入队次数就可以了。

因为操作动态内存比较慢,开了O2

貌似用静态数组+快读可以卡过去的。

就这样哇……

代码……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

#pragma GCC optimize("O2")

using LL=long long;

const int inf=0x7fffffff;

class GetLenth
{
private:
int PotNum;

typedef struct EdgeNode
{
int to,val;
EdgeNode *next;

EdgeNode(int v,EdgeNode *nxt,int w):to(v),val(w)
{
next=nxt;
}
~EdgeNode()
{
if(next!=nullptr)
delete next;
}
}*Edge;

Edge *head=nullptr;

inline void add(int u,int v,int w)
{
head[u]=new EdgeNode(v,head[u],w);
if(w>=0)
head[v]=new EdgeNode(u,head[v],w);
}

int *dis,*cnt;
bool *flag;

bool SPFA(int s)
{
dis[s]=0;
std::queue<int> que;
que.push(s);
flag[s]=1;
while(!que.empty())
{
int from=que.front();
que.pop();
flag[from]=0;
for(Edge node=head[from];node!=nullptr;node=node->next)
{
int to=node->to;
if(dis[to]>dis[from]+node->val)
{
dis[to]=dis[from]+node->val;
if(!flag[to])
{
cnt[to]++;
que.push(to);
flag[to]=1;
if(cnt[to]>=PotNum)
return true;
}
}
}
}
return false;
}

public:
GetLenth(int n):PotNum(n)
{
head=new Edge[n+10];
dis=new int[n+10];
for(int i=1;i<=n;i++)
dis[i]=inf;
flag=new bool[n+10];
cnt=new int[n+10];
std::memset(head,0,(n+10)*sizeof(Edge));
std::memset(flag,0,(n+10)*sizeof(bool));
std::memset(cnt,0,(n+10)*sizeof(int));
}

~GetLenth()
{
delete [] head;
delete [] dis;
delete [] flag;
delete [] cnt;
}

void input_edge(int m)
{
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
}

void Judge(int s)
{
if(SPFA(s))
puts("YE5");
else
puts("N0");
}
};

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
GetLenth *get_lenth=new GetLenth(n);
get_lenth->input_edge(m);
get_lenth->Judge(1);
delete get_lenth;
}

return 0;
}