你有 $n$ 个砝码，均为 $1 \texttt g$，$2 \texttt g$ 或者 $3 \texttt g$。你并不清楚每个砝码的重量，但你知道其中一些砝码重量的大小关系。

你把其中两个砝码 $A$ 和 $B$ 放在天平的左边，需要另外选出两个砝码放在天平的右边。

问：有多少种选法使得天平的左边重 ($c_1$)、一样重 ($c_2$)、右边重 ($c_3$)？(只有结果保证惟一的选法才统计在内)

输入格式

第一行包含三个正整数 $n, A, B$ ($4 \leq n \leq 50; 1 \leq A, B \leq n; A \neq B$)，砝码编号为 $1 \sim n$。

以下 $n$ 行包含重量关系矩阵，其中第 $i$ 行第 $j$ 个字符表示砝码 $i$ 与砝码 $j$ 之间的关系，其中加号 $\texttt +$ 表示砝码 $i$ 比砝码 $j$ 重，减号 $\texttt -$ 表示砝码 $i$ 比砝码 $j$ 轻，等号 $\texttt =$ 表示砝码 $i$ 和砝码 $j$ 一样重，问号 $\texttt ?$ 表示二者的关系未知。保证关系矩阵满足反对称性，且存在一种情况符合该矩阵。

输出格式

题解

由于 $n$ 并不是很大，因此枚举无序组 $(i, j)$，其中 $A, B, i, j$ 互不相等，我们就是要找有多少对这样的 $(i, j)$ 满足 $w_A + w_B > w_i + w_j$ 恒成立，等于和小于同理。

$w_A + w_B > w_i + w_j$ 恒成立，这个式子并不好处理，但是我们可以将它作一个恒等变形，变成 $w_A - w_i > w_j - w_B$ 恒成立。那么也就是说无论 $w_A, w_B, w_i, w_j$ 怎么取都要满足上式，即 $w_A - w_i$ 的最小值大于 $w_j - w_B$ 的最大值。

这样一来，我们需要知道对于任意的 $i, j$，$w_i - w_j$ 的最大/小值，由于 $1 \leq w_i \leq 3$，于是它们均有一个下界 $-2$ 和上界 $2$，当然这个界太松了。

于是对于每个 (非问号) 关系，比如 $w_i > w_j$，(由于离散性) 此时我们可以将 $w_i - w_j$ 的下界更新为 $1$；同样，如果 $w_i < w_j$，可以将 $w_i - w_j$ 的上界更新为 $-1$；当然如果 $w_i = w_j$，那么 $w_i - w_j$ 的上下界均为 $0$。

那么最后求任意的上下界简单了，直接使用 Floyd 算法即可。注意求下界时取 $\min$，比如 $w_i - w_j < a, w_j - w_k < b \wedge w_i - w_k < c$，那么有 $w_i - w_k < \min \{a + b, c\}$，当然求上界就是用 $\max$ 啦。

最后就是判断的问题。如果 $w_A + w_B > w_i + w_j$，那么它等价于 $\inf (w_A - w_i) > \sup (w_j - w_B)$；如果 $w_A + w_B < w_i + w_j$，就等价于 $\sup (w_A - w_i) < \inf (w_j - w_B)$。

两端相等的情况略有复杂，因为我们需要知道明确的关系：比如，$w_A - w_i$ 已知，$w_j - w_B$ 已知，且它们的值相等，此即 $\sup (w_A - w_i) = \inf (w_A - w_i) = \sup (w_j - w_B) = \inf (w_j - w_B)$。

代码

#include <bits/stdc++.h>
#define N 68
using namespace std;

int n, A, B;
int i, j, k;
int gt, eq, lt;
int lb[N][N], ub[N][N];
// lb[i][j]: the lower_bound of i - j, ub[i][j]: the upper_bound of i - j
char str[N];

inline void up(int &x, const int y) {x < y ? x = y : 0;}
inline void down(int &x, const int y) {x > y ? x = y : 0;}

int main(){
    scanf("%d%d%d", &n, &A, &B);
    for(i = 1; i <= n; ++i)
        for(scanf("%s", str), j = 1; j <= n; ++j){
            if(i == j) {lb[i][i] = ub[i][i] = 0; continue;}
            switch(str[j - 1]){
                case 61: {lb[i][j] = ub[i][j] = 0; break;}
                case 43: {lb[i][j] = 1; ub[i][j] = 2; break;}
                case 45: {lb[i][j] = -2; ub[i][j] = -1; break;}
                default: {lb[i][j] = -2; ub[i][j] = 2; break;}
            }
        }
    for(k = 1; k <= n; ++k)
        for(i = 1; i <= n; ++i)
            for(j = 1; j <= n; ++j){
                up(lb[i][j], lb[i][k] + lb[k][j]);
                down(ub[i][j], ub[i][k] + ub[k][j]);
            }
    for(i = 1; i < n; ++i)
        if(i != A && i != B)
            for(j = i + 1; j <= n; ++j)
                if(j != A && j != B){
                    if(lb[A][i] > ub[j][B] || lb[A][j] > ub[i][B]) ++gt;
                    if(ub[A][i] < lb[j][B] || ub[A][j] < lb[i][B]) ++lt;
                    if(ub[A][i] == lb[A][i] && lb[A][i] == ub[j][B] && ub[j][B] == lb[j][B] ||
                       ub[A][j] == lb[A][j] && lb[A][j] == ub[i][B] && ub[i][B] == lb[i][B]) ++eq;
                }
    printf("%d %d %d\n", gt, eq, lt);
    return 0;
}

坑

坑1：注意对于 $i = j$，数据给的关系仍有可能是 $\texttt ?$ (但不可能是 $\texttt +$ 或 $\texttt -$)，然而实际的关系显然是 $\texttt =$，因此需要特判为等号。

坑2：最后判断时，不能 $A$ 只和 $i$ 配对。假如枚举了无序组 $(i, j)$ 后，题目给的关系是 $w_A = w_j, w_B = w_i$，那么把它们俩放上去显然是相等的。但是算法中 $w_A - w_i$ 并不是确定的，也就是说，$A$ 也要和 $j$ 去配对尝试 (三种情况都要哦)。

题目描述

输入格式

输出格式

题解

代码

坑