突破负环检测的盲区：利用超级源点的策略

在刷洛谷或者 Codeforces 的负环题时，你是否遇到过这种诡异的情况：代码逻辑明明和题解一模一样，SPFA 跑得飞快且顺利收敛，结果一提交——全红（WA）。

原因可能很简单：你的负环，躲在了你“看不见”的地方。

1. 致命的盲区：起点 1 的局限性

大多数选手的习惯写法是：

    dist[1] = 0; q.push(1); vis[1] = true;

逻辑漏洞： 如果图是不连通的（或者从节点 1 出发无法到达某个连通分量），而负环恰好就在那个你到达不了的区域，SPFA 永远不会触发松弛操作，更别提判定负环了。

结论： 负环判定不是“求从 1 出发的最短路是否存在负环”，而是“判定整张图中是否存在负环”。

2. 解决方案 A：建立“超级源点”

这是一个极其经典的建模技巧。

操作方法：

虚拟一个不存在的节点 $S$（编号通常为 $0$ 或 $n+1$）。
让 $S$ 向图中所有的节点 $1 \dots n$ 连一条权值为 $0$ 的有向边。
从 $S$ 开始跑一次 SPFA。

数学本质： 这样保证了从 $S$ 出发可以到达图中的任何一个角落。如果图中存在任何一个负环，它一定会被捕捉到。

3. 解决方案 B：全员入队法 (更推荐的写法)

为了省去建虚点的麻烦，我们通常采用更高效的初始化方式：

// 核心伪代码：判负环的正确初始化
for (int i = 1; i <= n; ++i) {
    dist[i] = 0;    // 初始距离全部设为 0
    vis[i] = true;  // 标记全部在队列中
    q.push(i);      // 将所有节点一次性全部压入队列
}

while (!q.empty()) {
    int u = q.front(); q.pop(); vis[u] = false;
    // ... 后续正常的松弛与 cnt[v] >= n 判定
}

为什么这样做是正确的？ 这相当于我们同时开启了 $n$ 个起点的搜索。只要图中任何位置存在负环，由于所有点都在队列里，松弛操作会像多米诺骨牌一样连锁反应，最终指向那个矛盾的环。

在差分约束系统中，这个坑点也存在。如果你的题目要求判断不等式组是否有解，而你只从一个点出发，漏掉的可能不仅仅是一个负环，而是整个系统的合法性判定。

金句提炼： “不能只盯着起点，要统观全局。”