A/B's Blog

莫道桑榆晚,为霞尚满天。

P3385 【模板】负环【DFS-SPFA】

题目描述

暴力枚举/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;
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注