P3385 【模板】负环

题目描述

暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索

输入输出格式

输入格式：

第一行一个正整数T表示数据组数，对于每组数据：

第一行两个正整数N M，表示图有N个顶点，M条边

接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）

输出格式：

共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。

输入输出样例

输入样例#1：复制

输出样例#1：复制

N0
YE5

说明

N,M,|w|≤200 000；1≤a,b≤N；T≤10 建议复制输出格式中的字符串。

此题普通Bellman-Ford或BFS-SPFA会TLE

code

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 const int N = 500100;
 5 struct Edge{
 6     int to,nxt,w;
 7 }e[N];
 8 int head[N],tot,n,m,dis[N];
 9 bool vis[N];
10 
11 inline int read() {
12     int x = 0,f = 1;char ch = getchar();
13     for (; ch<'0'||ch>'9'; ch = getchar())
14         if (ch=='-') f = -1;
15     for (; ch>='0'&&ch<='9'; ch = getchar())
16         x = x*10+ch-'0';
17     return x*f;
18 }
19 inline void add_edge(int u,int v,int w) {
20     e[++tot].to = v,e[tot].nxt = head[u],e[tot].w = w,head[u] = tot;
21 }
22 bool spfa(int u) {
23     vis[u] = true;
24     for (int i=head[u]; i; i=e[i].nxt) {
25         int v = e[i].to,w = e[i].w;
26         if (dis[v] > dis[u]+w) {
27             if (vis[v]) return true;
28             dis[v] = dis[u]+w;
29             if (spfa(v)) return true;
30         }
31     }
32     vis[u] = false;
33     return false;    
34 }
35 int main() {
36     
37     int T = read();
38     while (T--) {
39         memset(head,0,sizeof(head));
40         memset(dis,0x3f,sizeof(dis)); // 可以是0 
41         memset(vis,false,sizeof(vis));
42         tot = 0;
43         n = read(),m = read();
44         for (int u,v,w,i=1; i<=m; ++i) {
45             u = read(),v = read(),w = read();
46             if (w < 0) add_edge(u,v,w);
47             else add_edge(u,v,w),add_edge(v,u,w);
48         }
49         bool flag = false;
50         for (int i=1; i<=n; ++i) 
51             if (spfa(i)) {flag = true;break;}
52         if (flag) puts("YE5");
53         else puts("N0");
54     }    
55     return 0;
56 }