基于Bellman-Ford判断差分约束方程组是否有解的代码问题排查

思路评估 #

你将方程组转化为图结构的核心思路是正确的，本质属于差分约束系统的可行性校验场景：等式x_i = x_j + c可拆解为两个不等式x_i - x_j ≤ c和x_j - x_i ≤ -c，刚好对应你添加的两条带权有向边。一旦图中出现权值和不为0的环，就对应方程组矛盾，而这类环必然存在反向的负权和环，确实可以通过Bellman-Ford算法检测负环来判断可行性。

代码错误点 #

1. 单源点无法覆盖不连通分量 #

你仅选择0号节点作为源点，如果图存在多个互不连通的分量，其他分量内的节点距离始终为初始的INF，不会参与松弛运算，即使这些分量内部存在负环也无法被检测到。
反例测试输入：

1
4 3
1 2 1
3 4 1
4 3 1

上述输入中3、4节点构成矛盾环，方程组本应输出NO，但你的代码仅能访问1、2所在的连通分量，会错误输出YES。

2. 缺少INF判断导致整数溢出 #

你定义的INF = 1<<30已经接近int类型的上限，松弛运算时没有判断distances[from]是否为INF，当from节点未被访问过时，distances[from] + weight可能溢出为负数，触发错误的松弛逻辑，导致距离计算异常。

修复方案 #

1. 新增超级源点：新增编号为N的节点，给该节点到所有0~N-1节点各添加一条权值为0的边，确保所有连通分量都能被遍历到，总节点数变为N+1，松弛次数对应调整为N次。
2. 增加INF校验：松弛前先判断distances[from]是否不等于INF，再执行后续的松弛逻辑。

修复后参考代码 #

#include<iostream>
#include<vector>
using namespace std;

#define INF (1<<29) // 适当调小INF避免溢出
int main(){
    int T;
    cin>>T;
    while(T--){
        int N, M;
        cin>>N>>M;
        vector<vector<int>> edges;
        for (int i=0;i<M;++i){
            int first, second, third;
            cin>>first>>second>>third;
            first--;second--;
            edges.push_back({first,second,third});
            edges.push_back({second,first,-third});
        }
        // 加超级源点N到所有节点的边
        for(int i=0;i<N;++i){
            edges.push_back({N, i, 0});
        }
        vector<int> distances(N+1, INF);
        distances[N] = 0;
        // 总节点数是N+1，松弛N次
        for (int i=1;i<=N;++i){
            for (int j=0;j<edges.size();++j){
                int from = edges[j][0];
                int to = edges[j][1];
                int weight = edges[j][2];
                if (distances[from] != INF && distances[from]+weight < distances[to]){
                    distances[to] = distances[from] + weight;
                }
            }
        }
        int flag = 0;
        for (int j=0;j<edges.size();++j){
            int from = edges[j][0];
            int to = edges[j][1];
            int weight = edges[j][2];
            if (distances[from] != INF && distances[from]+weight < distances[to]){
                flag = 1;
                break;
            }
        }
        if (flag==1){
            cout << "NO" << endl;
        }
        else{
            cout << "YES" << endl;
        }
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者kumarp