Wormholes

判断负圈的版子题

之前的题用Bellman法判断过了。
这里就用spfa判断一下负圈吧。

用spfa判断负圈的方法有两种：
1.记录节点入队的次数，若次数>n-1则有负圈
2.记录起点到节点经历的边数，若边数>n-1则有负圈（也可以理解为途经的节点数）

第二种会更快一点

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
const int max_n = 700;
const int max_m = 3000;
const int inf = 2e9;
struct edge{
    int to, cost, next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cost) {
    E[cnt].to = to;E[cnt].cost = cost;
    E[cnt].next = head[from];head[from] = cnt++;
}

int d[max_n];
int cct[max_n];
bool vis[max_n];
bool spfa(int s,int n) {
    fill(d, d + max_n, inf);
    fill(cct, cct + max_n, 0);
    fill(vis, vis + max_n, false);
    queue<int> que;que.push(s);
    d[s] = 0;vis[s] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();vis[u] = false;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                cct[e.to] = cct[u] + 1;
                if (cct[e.to] >= n)return true;
                if (vis[e.to])continue;
                vis[e.to] = true;
                que.push(e.to);
            }
        }
    }return false;
}

int N, M, W;
int main() {
    int tcase;scanf("%d", &tcase);
    while (tcase--) {
        fill(head, head + max_n, 0);cnt = 1;
        scanf("%d %d %d", &N, &M, &W);
        for (int i = 1, u, v, c;i <= M;++i) {
            scanf("%d %d %d", &u, &v, &c);
            add(u, v, c);add(v, u, c);
        }for (int i = 1, u, v, c;i <= W;++i) {
            scanf("%d %d %d", &u, &v, &c);
            add(u, v, -c);
        }spfa(1, N) ? printf("YES\n") : printf("NO\n");
    }
}