首先是我感觉我的建图和题解里的建图好像有点不一样，但是我感觉我这么建图然后差分约束没啥问题。有劳各位大佬在百忙之中帮忙看一下解答一下，我将向第一位给出正确解答的大佬发送 $20$ 元红包作为酬谢。万分感谢！

首先是我对差分约束建图的理解

首先是我对差分约束建图的理解（不知道对不对，可能在理解上就错了，恳请各位大佬帮忙指正）：

如果我们用 $val_i$ 表示节点 $i$ 的权值，则：

情况一（求最短路）

若存在若干对如下所示的关系：

$val_i \le val_j + C$（其中 $C$ 是一个常量），

则转换成图论模型后，应该建一条以节点 $j$ 为起点，以节点 $i$ 为终点的边权为 $C$ 的有向边。

建完边之后求最短路。

很明显，对于 $val_i \le val_j + C$，因为 $j \rightarrow i$ 存在一条直连的边权为 $C$ 的边，所以从节点 $j$ 出发到达节点 $i$ 的最短路径长度肯定小于等于 $C$ 的，满足给定的条件。

情况二（求最长路）

若存在的关系都描述为：

$val_i \ge val_j + C$

则其它条件都不变，建完边之后求最长路。

其次是这道题目的建图

因为这题涉及两个砝码差值的最大值和最小值，所以需要同时求最长路和最短路。

这里使用 floyd 算法把任意两点间的最短路和最长路都求出来。

这里：

• 用 $dx_{i,j}$ 表示从节点 $i$ 出发到达节点 $j$ 的最长路径长度；
• 用 $dm_{i,j}$ 表示从节点 $i$ 出发到达节点 $j$ 的最短路径长度。

然后接下来是考虑建图然后跑 floyd。

我们用 $s_{i,j}$ 表示输入的二维字符矩阵第 $i$ 行第 $j$ 列的那个字符，同时用 $val_i$ 表示砝码的重量，那么，根据 $s_{i,j}$ 的不同情况需要建不同的图，具体如下：

情况1：$s_{i,j} =$ '+'

当 $s_{i,j} =$ '+' 时，表示砝码 $i$ 比砝码 $j$ 重。

此时，有三种合法情况（因为砝码的重量只有可能是 $1$、$2$ 或 $3$ 克）：

1. $val_i = 3, val_j = 2$
2. $val_i = 3, val_j = 1$
3. $val_i = 2, val_j = 1$

可以发现，此时砝码 $i$ 至少比砝码 $j$ 重 $1$ 克，但不会比砝码 $j$ 重超过 $2$ 克。

此时可以得到如下两个不等式：

1. $val_i \ge val_j + 1$
2. $val_i \le val_j + 2$

此时令：

• $dx_{j, i} = 1$：表示在求最长路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $1$ 的有向边；
• $dm_{j, i} = 2$：表示在求最短路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $2$ 的有向边。

情况2：$s_{i,j} =$ '-'

当 $s_{i,j} =$ '-' 时，表示砝码 $i$ 比砝码 $j$ 轻。

此时，有三种合法情况：

1. $val_i = 1, val_j = 2$
2. $val_i = 1, val_j = 3$
3. $val_i = 2, val_j = 3$

可以发现，此时砝码 $i$ 至少比砝码 $j$ 轻 $1$ 克，但不会比砝码 $j$ 轻超过 $2$ 克。

此时可以得到如下两个不等式：

1. $val_i \ge val_j - 2$
2. $val_i \le val_j - 1$

此时令：

• $dx_{j,i} = -2$：表示在求最长路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $-2$ 的有向边；
• $dm_{j,i} = -1$：表示在求最短路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $-1$ 的有向边。

情况3：$s_{i,j} =$ '=' 或者 $i = j$

当 $i = j$ 或 $s_{i,j} =$ '=' 时，表示砝码 $i$ 和砝码 $j$ 的重量相等，此时

$val_i = val_j$

可以推导出如下两个不等式：

1. $val_i \ge val_j + 0$
2. $val_i \le val_j + 0$

此时令：

• $dx_{j,i} = 0$：表示在求最长路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $0$ 的有向边；
• $dm_{j,i} = 0$：表示在求最短路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $0$ 的有向边。

情况4：$s_{i,j} =$ '?'

当 $s_{i,j} =$ '?' 时，此时所有情况都是有可能的（即 $val_i \in \{1,2,3\}$ 且 $val_j \in \{1,2,3\}$），但砝码 $i$ 和砝码 $j$ 的质量相差不会超过 $2$ 克，继而可以推出如下两个不等式：

1. $val_i \ge val_j - 2$
2. $val_i \le val_j + 2$

此时令：

• $dx_{j,i} = -2$：表示在求最长路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $0$ 的有向边；
• $dm_{j,i} = 2$：表示在求最短路的图中，以节点 $i$ 为起点，节点 $j$ 为终点连一条长度为 $0$ 的有向边。

这样就建好图了，然后跑一遍 floyd。

跑完 floyd 之后：

• $dx_{j,i}$ 表示的是 $j$ 到 $i$ 的最长路径长度，它的实际含义是：$val_i - val_j$ 的最大值；
• $dm_{j,i}$ 表示的是 $j$ 到 $i$ 的最短路径长度，它的实际含义是：$val_i - val_j$ 的最小值。

最后是建完图之后枚举所有情况

因为天平的左边放的是砝码 $A$ 和 $B$，所以我这边设天平的右边放的是砝码 $i$ 和 $j$，并枚举 $i$ 和 $j$。

因为 ”选砝码 $i$ 和 $j$” 与 ”选砝码 $j$ 和 $i$” 是等价的，所以在枚举的时候是按照：

for i ← 1 to n-1
    for j ← i+1 to n

的方式来枚举，并且保证 $A, B, i, j$ 各不相同，这样能做到不重不漏。

然后是分情况讨论 $val_A + val_B$（即砝码 $A$ 和 $B$ 的重量之和）是否一定 大于、小于 或 等于 $val_i + val_j$（即砝码 $i$ 和 $j$ 的重量之和）。

情况1：天平的左边重

此时满足条件：

$val_A + val_B \gt val_i + val_j$

上式等价于：

• $val_A - val_i \gt val_j - val_B$，①
• 或 $val_A - val_j \gt val_i - val_B$，②

只需要 $val_A - val_i$ 的最小值大于 $val_j - val_B$ 的最大值， ① 式必然成立。

而 $dm_{i,A}$ 表示的就是$val_A - val_i$ 的最小值，$dx_{B,j}$ 表示的就是 $val_j - val_B$ 的最大值，所以只需要满足 $dm_{i,A} \gt dx_{B,j}$ 则 ① 式必然成立。

同理，只需要满足 $dm_{j,A} \gt dx_{B,j}$ 则 ② 式必然成立。

总结：

当 $dm_{i,A} \gt dx_{B,j}$ 或 $dm_{j,A} \gt dx_{B,j}$ 时，一定是天平的左边重。

情况2：天平的左右两边一样重

此时满足条件：

$val_A + val_B = val_i + val_j$

上式等价于：

• $val_A - val_i = val_j - val_B$，①
• 或 $val_A - val_j = val_i - val_B$，②

对于 ① 式，这等价于说 $i$ 到 $A$ 的距离是一个固定值，同时 $B$ 到 $j$ 的距离也是这一个固定值（无论是在最短路对应的图还是在最长路对应的图中），所以只需要满足 $dx_{i,A} = dm_{i,A} = dx_{B,j} = dm_{B,j}$ 则 ① 式必然成立。

同理，只需要满足 $dx_{j,A} = dm_{j,A} = dx_{B,i} = dm_{B,i}$ 则 ② 式必然成立。

总结：

当 $dx_{i,A} = dm_{i,A} = dx_{B,j} = dm_{B,j}$ 或 $dx_{j,A} = dm_{j,A} = dx_{B,i} = dm_{B,i}$ 时，一定是天平的左右两边一样重。

情况3：天平的右边重

此时满足条件：

$val_A + val_B \lt val_i + val_j$

上式等价于：

• $val_A - val_i \lt val_j - val_B$，①
• 或 $val_A - val_j \lt val_i - val_B$，②

只需要 $val_A - val_i$ 的最大值小于 $val_j - val_B$ 的最小值， ① 式必然成立。

而 $dx_{i,A}$ 表示的就是$val_A - val_i$ 的最大值，$dm_{B,j}$ 表示的就是 $val_j - val_B$ 的最小值，所以只需要满足 $dx_{i,A} \lt dm_{B,j}$ 则 ① 式必然成立。

同理，只需要满足 $dx_{j,A} \lt dm_{B,i}$ 则 ② 式必然成立。

总结：

当 $dx_{i,A} \lt dm_{B,j}$ 或 $dx_{j,A} \lt dm_{B,i}$ 时，一定是天平的左边重。

代码

根据上面的推导，编写的程序如下（但是错了，样例2都没对）：

为了写起来方便起见，下标从 $0$ 到 $n-1$。

#include <bits/stdc++.h>
using namespace std;
int n, A, B, dx[55][55], dm[55][55];
char s[55][55];

// 一个辅助的函数，用来判断4个数的数值是否相同
bool equal4(int a, int b, int c, int d) {
    return a == b && b == c && c == d;
}

int main() {
    scanf("%d%d%d", &n, &A, &B);
    A--, B--;
    for (int i = 0; i < n; i++)
        scanf("%s", s[i]);
    // 建图
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '+')
                dx[j][i] = 1, dm[j][i] = 2;
            else if (s[i][j] == '-')
                dx[j][i] = -2, dm[j][i] = -1;
            else if (i == j || s[i][j] == '=')
                dx[j][i] = dm[j][i] = 0;
            else // s[i][j] == '?'
                dx[j][i] = -2, dm[j][i] = 2;
        }
    }
    // floyd
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dx[i][j] = max(dx[i][j], dx[i][k] + dx[k][j]),
                dm[i][j] = min(dm[i][j], dm[i][k] + dm[k][j]);
    // 枚举 i 和 j
    int c1 = 0, c2 = 0, c3 = 0; // 和题目对应
    for (int i = 0; i < n; i++) {
        if (i == A || i == B) continue;
        for (int j = i+1; j < n; j++) {
            if (j == A || j == B) continue;
            if (dm[i][A] > dx[B][j] || dm[j][A] > dx[B][i])
                c1++;
            if (equal4(dx[i][A], dm[i][A], dx[B][j], dm[B][j]) || equal4(dx[j][A], dm[j][A], dx[B][i], dm[B][i]))
                c2++;
            if (dx[i][A] < dm[B][j] || dx[j][A] < dm[B][i])
                c3++;
        }
    }
    printf("%d %d %d\n", c1, c2, c3);
    return 0;
}

有劳各位大佬帮忙看一下哪里出问题了，我将向第一位给出正确解答的大佬发送 $20$ 元红包作为酬谢。万分感谢！