题解 P2850 【[USACO06DEC]虫洞Wormholes】

ljcljc · 2019-11-23 20:57:32 · 题解

一道负环的裸题, 基于SPFA (这个死了的算法),我们有两种思路：

(1)统计每个点入队的次数， 如果某个点入队n次， 说明存在负环；

(2)统计当前每个点的最短路中所包含的边数， 如果某个点的最短路所包含的边数大于等于n， 则说明存在负环；

我使用的是第二种写法：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 510;
const int M = 5500;
int n, m1, m2;
int cnt[N], vis[N], dis[N];
struct edge {
    int to, w;
};
vector<edge> G[M];

bool spfa() {
    queue<int> q;
    memset(cnt, 0, sizeof cnt);
    memset(vis, 0, sizeof vis);
    memset(dis, 0, sizeof dis);
    for(int i=1; i<=n; i++) {
        q.push(i);
        vis[i] = 1;
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=0; i<G[u].size(); i++) {
            int v = G[u][i].to;
            int w = G[u][i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n) return true;
                if(!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(G, 0, sizeof(G));
        scanf("%d %d %d", &n, &m1, &m2);
        while(m1--) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back((edge){v, w});
            G[v].push_back((edge){u, w});
        }
        while(m2--) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back((edge){v, -w});
        }
        if(spfa()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}