题目描述

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

输入输出格式

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

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

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

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

输入输出样例

输入样例#1：复制

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出样例#1：复制

N0
YE5

说明

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

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

这题有几个坑..第一，输出的是N'零'和YE'五'...

第二，因为有双向边，所以存边的数组要开两倍...

不过是没坑到我啦，我可是身经百战了（大雾）

这个得用dfs-spfa，bfs要把一个负环过N次才能察觉出来

O(ke)的期望复杂度，也就真的只是期望了...

dfs则不同，检测把一个点过了两次就行了

因为一条最短路径上不可能让一个点同时出现两次

暂且这么理解..要说有什么被坑到的话，就是我把addedge的v把t给赋值了进去

害得我调了好久...Orz

?
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
#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 400004
#define MAXM 400004
#define INF 2147483
using namespace std;
int n, m;
int t;
int ec;
bool negative, vis[MAXN];
int head[MAXM], dis[MAXN];
struct edge{
    int next, to, v;
}e[MAXM];
void init(){
    ec = 0;
    negative = 0;
    for (int i = 0; i < MAXM; i++){
        vis[i] = 0;
        dis[i] = 0;
        head[i] = -1;
    }
}
void spfa(int v){
    for (int i = head[v]; i != -1; i = e[i].next){
        if (negative) return;
        int to = e[i].to;
//      cout << dis[to] << ' ' << dis[v] << " + " << e[i].v << endl;
        if (dis[to] > dis[v] + e[i].v){
            dis[to] = dis[v] + e[i].v;
            if (vis[to]){
                negative = 1;
//              cout << "n" << to << ' ' << v << endl;
                return;            
            }else{
                vis[v] = 1;
                spfa(to);
            }
        }
    }
    vis[v] = 0;
}
void addedge(int s, int t, int v){
    e[ec].to = t;
    e[ec].v = v;
    e[ec].next = head[s];
    head[s] = ec++;
}
int main(){
    scanf("%d", &t);
    while(t--){
        init();
        scanf("%d%d", &n, &m);
        int a, b, w;
        for (int i = 0; i < m; i++){
            scanf("%d%d%d", &a, &b, &w);
            if (w < 0){
                addedge(a, b, w);
            }else{
                addedge(a, b, w);
                addedge(b, a, w);
            }
        }
        for (int i = 1; i <= n; i++){
            spfa(i);
            if(negative) break;
        }
        if (negative) printf("YE5\n");
        else printf("N0\n");
    }
    return 0;
}