首页 > 代码库 > 判断是否存在负环

判断是否存在负环

2024-07-07 09:21:13   236人阅读

?
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 <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
#define maxn 100010
#define INF 0x7fffffff
#define inf 100000000
#define MOD 1000000007
#define ULL unsigned long long
#define LL long long
 
using namespace std;
 
struct edge
{
    int s, v, w;
}p[6100];
 
int n, m, w, d[510], num_p;
 
void addedge(int a, int b, int c) {
    p[num_p].s = a;
    p[num_p].v = b;
    p[num_p].w = c;
    ++ num_p;
}
 
bool bellom_form() {
    for(int i = 1; i <= n; ++ i) {
        d[i] = inf;
    }
    d[1] = 0;
    for(int i = 0; i < n-1; ++ i) {
        for(int j = 0; j < num_p; ++ j) {
            if(d[p[j].v] > d[p[j].s]+p[j].w) {
                d[p[j].v] = d[p[j].s]+p[j].w;
            }
        }
    }
    for(int i = 0; i < num_p; ++ i) {
        if(d[p[i].v] > d[p[i].s]+p[i].w) {
            return true;
        }
    }
    return false;
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t --) {
        scanf("%d%d%d", &n, &m, &w);
        num_p = 0;
        for(int i = 0; i < m; ++ i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            addedge(a, b, c);
            addedge(b, a, c);
        }
        for(int i = 0; i < w; ++ i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            addedge(a, b, -c);
        }
        if(bellom_form()) puts("YES");
        else puts("NO");
    }
    return 0;
}

　　


联系
我们