Bellman-Ford算法判断负权回路程序解析

"这是关于NOIP2004复习资料中涉及的Bellman-Ford算法的程序清单，用于判断无向图是否存在负权回路。" Bellman-Ford算法是一种用于解决图论问题的动态规划算法，主要用途是寻找图中的最短路径。在这个程序中，它被用来检测是否存在负权边构成的回路。该算法的核心思想是通过松弛操作逐步更新图中所有顶点的距离。如果在经过n-1次迭代后仍然能找到一条边使得终点的路径长度小于起点加上这条边的权重，那么就可能存在一个负权回路。 程序开始时，首先进行初始化，读取输入文件`bellman.in`中的图信息，包括顶点数量`n`和边的数量`e`，以及每条边的起始点`x`、终点`y`和权重`t`。初始状态下，除了源点（这里假设为顶点1）的距离设为0，其他所有顶点的距离都被赋值为无穷大（用十六进制$6F`表示）。 接下来，算法进入主循环，进行n-1次迭代。在每次迭代中，遍历所有的边，如果发现可以通过一条边将终点的路径长度缩短，就进行更新。这一步称为松弛操作。 在第n-1次迭代结束后，算法进入一个额外的检查阶段，再次遍历所有边。如果此时依然存在可以缩短的边，即有某个点`x`到`y`的路径通过边`x->y`可以比当前的`d[y]`更短，说明存在负权回路，因为正常情况下在n-1次迭代后应该已经找到所有最短路径。如果在这个阶段找到了这样的边，`main`函数返回`false`，表示存在负权回路；否则，返回`true`，表明图中没有负权回路。 此外，程序还包含了一个求解最大公约数的函数`gcd(a,b;var x,y)`，它使用扩展欧几里得算法来同时计算两个数的最大公约数`gcd`以及满足`ax + by = gcd`的一组解`(x0, y0)`。 这个程序展示了如何利用Bellman-Ford算法来检测无向图中的负权回路，并结合了求最大公约数的算法，是图论和数论问题的一个实际应用示例。