题解：[USACO06DEC] Wormholes G

完整题面

一、前置知识

• 负环（Bellman-Ford 或 SPFA+超级源点）

二、题目大意

给定一个$n$个点$m$条正双向边$q$条负单向边，判断图上有没有负环

三、思考问题

不用思考，求负环模板题

四、完整代码

#include <cstdio>
#include <cstring>
using namespace std;

int T;
int n, m, q;

int u[20005], v[20005], w[20005], tot;

int dis[505];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &q);
        tot = 0;
        for (int i = 1; i <= m; i++) {
            tot++;
            scanf("%d%d%d", &u[tot], &v[tot], &w[tot]);
            u[tot + 1] = v[tot];
            v[tot + 1] = u[tot];
            w[tot + 1] = w[tot];
            tot++;
        }
        for (int i = 1; i <= q; i++) {
            tot++;
            scanf("%d%d%d", &u[tot], &v[tot], &w[tot]);
            w[tot] = -w[tot];
        }

        memset(dis, 0x3f, sizeof(dis));
        dis[1] = 0;
        bool flag = true;
        for (int k = 1; k < n; k++) {
            flag = true;
            for (int i = 1; i <= tot; i++)
                if (dis[v[i]] > dis[u[i]] + w[i]) {
                    dis[v[i]] = dis[u[i]] + w[i];
                    flag = false;
                }
            if (flag) {
                puts("NO");
                break;
            }
            if (k == n - 1) {
                puts("YES");
                break;
            }
        }
    }
    return 0;
}

提交看看

五、代码优化

1. 更改存图方式

2. 将Bellman-Ford改为SPFA提高效率

3. 修改变量名称

4. 添加注释，增加可读性

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

const int INF = 0x3f3f3f3f;
const int MAXN = 505;

int T;
int n, m, q;

struct Edge {
    int v, w; // v: 目标节点, w: 边权
};

vector<Edge> graph[MAXN]; // 邻接表存储图
int dis[MAXN];            // 距离数组
int cnt[MAXN];            // 记录每个节点的入队次数
bool inQueue[MAXN];       // 记录节点是否在队列中

bool SPFA(int start) {
    // 初始化距离数组
    memset(dis, INF, sizeof(dis));
    dis[start] = 0;

    // 初始化队列和标记数组
    queue<int> q;
    q.push(start);
    inQueue[start] = true;
    cnt[start] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false; // 标记为不在队列中

        // 遍历所有邻接边
        for (const auto& edge : graph[u]) {
            int v = edge.v, w = edge.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;
                    // 如果某个节点入队次数超过 n 次，说明存在负权环
                    if (cnt[v] > n) {
                        return true;
                    }
                }
            }
        }
    }
    return false; // 没有负权环
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &q);

        // 初始化邻接表
        for (int i = 0; i <= n; i++) {
            graph[i].clear();
        }
        
        // 建立超级源点
        for (int i = 1; i <= n; i++) {
            graph[0].push_back({i, 0});
        }

        // 读取无向图的边
        for (int i = 0; i < m; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }

        // 读取查询的边（负权）
        for (int i = 0; i < q; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            graph[u].push_back({v, -w}); // 添加负权边
        }

        // 初始化入队次数和队列标记
        memset(cnt, 0, sizeof(cnt));
        memset(inQueue, false, sizeof(inQueue));

        // 使用 SPFA 检测负权环
        bool hasNegativeCycle = SPFA(0);

        // 输出结果
        puts(hasNegativeCycle ? "YES" : "NO");
    }
    return 0;
}

建议、代码来源：deepseek（已验证代码正确性）

就好了