洛谷 P3385 【模板】负环

// 洛谷 P3385 【模板】负环 —— ★ 这一版就能 AC
//
// 问的是「**从顶点 1 出发能到达**的负环」——正是本章第 1 步那件事，
// 而 SPFA / Bellman-Ford **天生只报告 s 能走到的负环**（dist 从 s 初始化）。
//
// 三处这道题独有的细节：
//   ① 读边：w ≥ 0 存双向，w < 0 只存 u → v —— **正负号说了算**
//   ② cnt[v] 记的是「最短路用了几条边」，≥ n 就有负环（n 个点的简单路最多 n−1 条边）
//   ③ 多组数据，每组都要把 g / dist / cnt / inq 清干净

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int e = 0; e < m; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            if (w >= 0) g[v].push_back({u, w});      // ★ 正负号说了算
        }

        const int INF = 0x3f3f3f3f;
        vector<int> dist(n + 1, INF), cnt(n + 1, 0);
        vector<char> inq(n + 1, 0);
        queue<int> q;
        dist[1] = 0;
        inq[1] = 1;
        q.push(1);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front();
            q.pop();
            inq[u] = 0;                              // ★ 出队就清（本章第 7 步）
            for (auto [v, w] : g[u])
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    cnt[v] = cnt[u] + 1;             // ★ 记的是「几条边」，不是「入队几次」
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法①：边一律存两遍 —— ★★★ 这一页的主线
//
// 「无向图存两遍」是练了二十道题练出来的手感，而这道题的题面把规则改了：
//     若 w ≥ 0，存 u→v 和 v→u；
//     若 w < 0，**只存 u→v**。
//
// 一律存双向的后果是灾难性的：一条 w < 0 的边被存成来回两条，
// 那 u → v → u 绕一圈就是 2w < 0 —— **它自己就是一个负环**。
// ⇒ 只要输入里有一条从 1 号点走得到的负权边，它就无脑输出 YES。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int e = 0; e < m; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            g[v].push_back({u, w});          // ✗ 不看正负号，一律两遍
        }
        const int INF = 0x3f3f3f3f;
        vector<int> dist(n + 1, INF), cnt(n + 1, 0);
        vector<char> inq(n + 1, 0);
        queue<int> q;
        dist[1] = 0; inq[1] = 1; q.push(1);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, w] : g[u])
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法②：从**所有点**出发（等价于加一个超级源点）
//
// 这是判「图里有没有负环」的标准写法 —— 而这道题问的是
// 「**从顶点 1 出发能到达**的负环」。
// ⇒ 图的角落里躺着一个 1 号点过不去的负环时，它会多报一个 YES。
//
// ★★★ 而下一道 [P2850] 问的恰恰是「不管从哪出发」——
//     同一段代码，在那道题上是正解，在这道题上是错的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int e = 0; e < m; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            if (w >= 0) g[v].push_back({u, w});
        }
        vector<int> dist(n + 1, 0), cnt(n + 1, 0);   // ✗ 所有点初值 0、全部入队
        vector<char> inq(n + 1, 1);
        queue<int> q;
        for (int i = 1; i <= n; i++) q.push(i);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, w] : g[u])
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法③：多组数据没清干净
//
// 题面第一句就是「**本题单测试点有多组测试数据**」。
// 这一版把 dist / cnt / inq 提到了循环外面（很多人写惯了全局数组就是这样），
// 于是上一组的 dist 会当成这一组的初值 —— 而上一组可能刚跑出一堆负数。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 2005;
int dist_[MAXN], cnt[MAXN];
char inq[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int i = 0; i < MAXN; i++) dist_[i] = INF;    // ✗ 只在最外面初始化了一次
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int e = 0; e < m; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            if (w >= 0) g[v].push_back({u, w});
        }
        queue<int> q;
        dist_[1] = 0; inq[1] = 1; q.push(1);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, w] : g[u])
                if (dist_[u] + w < dist_[v]) {
                    dist_[v] = dist_[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ✗ 错法⑤：链式前向星的边数组**按 m 开**
//
// 题面「提示」那一节只有一句话：**「请注意，m 不是图的边数。」**
// 它说的就是这件事：w ≥ 0 的那些行**各要存两条**边 ⇒ 真实边数最多 2m = 6000。
//
// ⚠ 数组开小是未定义行为（越界写别人的内存），演示不出可复现的结果 ——
//    所以这一版**加了一个出口**：一旦要写的下标越过数组，就打 `OVERFLOW` 退出。
//    真交上去的话，那儿是一个安静的越界写。

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 3005;                      // ✗ 按题面的 m ≤ 3000 开
int head_[2005], nxt[MAXM], to_[MAXM], wt[MAXM], tot;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        tot = 0;
        for (int i = 0; i <= n; i++) head_[i] = -1;
        auto add = [&](int u, int v, int w) {
            if (tot >= MAXM) { cout << "OVERFLOW\n"; exit(0); }
            to_[tot] = v; wt[tot] = w; nxt[tot] = head_[u]; head_[u] = tot++;
        };
        for (int e = 0; e < m; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
            if (w >= 0) add(v, u, w);
        }
        const int INF = 0x3f3f3f3f;
        vector<int> dist(n + 1, INF), cnt(n + 1, 0);
        vector<char> inq(n + 1, 0);
        queue<int> q;
        dist[1] = 0; inq[1] = 1; q.push(1);
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (int i = head_[u]; i != -1; i = nxt[i]) {
                int v = to_[i], w = wt[i];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { neg = true; break; }
                    if (!inq[v]) { inq[v] = 1; q.push(v); }
                }
            }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}

// ？错法④：cnt 记「入队几次」而不是「最短路用了几条边」
//
// 这是流传很广的另一种写法。它到底对不对，这一页量了一遍 —— 结论写在页面上。
// （本书那条老规矩：**流传很广的提醒，量完之后可能要反过来说。**）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> g(n + 1);
        for (int e = 0; e < m; e++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].push_back({v, w});
            if (w >= 0) g[v].push_back({u, w});
        }
        const int INF = 0x3f3f3f3f;
        vector<int> dist(n + 1, INF), cnt(n + 1, 0);
        vector<char> inq(n + 1, 0);
        queue<int> q;
        dist[1] = 0; inq[1] = 1; q.push(1); cnt[1] = 1;
        bool neg = false;
        while (!q.empty() && !neg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, w] : g[u])
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (!inq[v]) {
                        inq[v] = 1;
                        q.push(v);
                        if (++cnt[v] >= n) { neg = true; break; }   // ？数的是入队次数
                    }
                }
        }
        cout << (neg ? "YES" : "NO") << "\n";
    }
    return 0;
}