0

我遇到了一个问题，它要求我找到任何给定顶点对之间最便宜的路径的最大值。我为解决方案实现了 Floyd Warshall 算法。但是我的程序中有一个奇怪的错误。我使用 intmax_t 来避免溢出，但是如果我使用 INTMAX_MAX 而不是 INT_MAX 来表示两个顶点没有直接连接，那么我会得到错误的答案。为什么会这样？

#include <bits/stdc++.h>
using namespace std;
struct _ { ios_base::Init _i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;

#define endl '\n'
#define int intmax_t
#define in(x) for (auto& i: x)
#define test int _t; cin >> _t; for (int i=1; i<=_t; i++) {

signed main()
{
    int v, e, ans=INT_MIN;
    cin >> v >> e;
    int g[v+1][v+1];
    for (int i=1; i<=v; i++)
        for (int j=1; j<=v; j++)
            g[i][j]=INT_MAX;
    for (int i=0; i<e; i++)
    {
        int x, y, p;
        cin >> x >> y >> p;
        g[x][y]=g[y][x]=p;
    }
    for (int i=1; i<=v; i++)
        for (int j=1; j<=v; j++)
            for (int k=1; k<=v; k++)
                g[j][k]=min(g[j][k], g[j][i]+g[i][k]);
    for (int i=1; i<=v; i++)
        for (int j=1; j<=v; j++)
            if (g[i][j]!=INT_MAX && i!=j)
                ans=max(ans, g[i][j]);
    cout << ans;
}

如果我将 INT_MIN 替换为 INTMAX_MIN 并将 INT_MAX 替换为 INTMAX_MAX，则会得到不正确的结果。

示例案例：

使用 INT_MAX：http: //ideone.com/ffmv7P

使用 INTMAX_MAX：http: //ideone.com/vjMCuE

附录：这个程序是专门为解决竞争性编程问题而编写的。请将您的“正确编码实践”建议留给自己。如果您愿意回答，您会发现预处理器指令在这种情况下对可读性造成的影响很小或没有问题。他们在那里是有原因的，我并不愚蠢。如果您没有竞争性编程经验，请不要将责任归咎于我。谢谢。

4

2 回答 2

1

您正在添加数字并有可能溢出。使用时，INT_MAX您正在使用可能低于范围的数字初始化单元格intmax_t（这是单元格的真实类型）。这很INT_MAX+INT_MAX可能适合intmax_t而不会溢出，而INTMAX_MAX+INTMAX_MAX绝对不会。

您遇到整数溢出，理论上它具有未定义的行为。很可能在现实中它不能很好地与比较一起工作，因为整数溢出会包装成负数，使得INTMAX_MAX+INTMAX_MAX小于INTMAX_MAX（它甚至可以变成负数）。

如果您的编译器int具有相同的范围intmax_t（这并非不切实际），那么您的代码在这两种情况下都应该失败。

于 2016-01-07T07:42:19.597 回答
1

您显然不能将 INTMAX_MAX 存储在 int 类型的变量中。你会得到一个溢出，这会导致未定义的行为。在实践中，您通常会得到 INTMAX_MAX 的最后 32 位，它们与 (int) -1 的位模式相同。

另一方面，将 int 与 INTMAX_MAX 进行比较意味着 int 将被转换为 intmax_t，但只要类型不同（实际上它们是不同的），int 就永远不会等于 INTMAX_MAX。

于 2016-01-07T08:49:04.553 回答