Description：

有 $n$ 个砝码均为 $1$ 克 $2$ 克或 $3$ 克。知道一些砝码重量的大小关系。把砝码 $A $ 和 $B $ 放在天平的左边，另外选出两个砝码放在天平的右边。问有多少种选法使得天平的左边重、一样重、右边重。

$1\leqslant n \leqslant 50$

Solution：

其实也不算差分约束，只是一个非常神奇的差分建图。

设 $maxbound[i][j]$ 和 $minbound[i][j]$ 表示 $minbound[i][j]\leqslant i-j\leqslant maxbound[i][j]$ ，那么可以先把已知的边建出来，然后我们发现有一个关系是 $maxbound[i][j]\leqslant maxbound[i][k]+maxbound[k][j]$ ，这个也很好理解，有一些限制性更强的关系限制了他们，同理 $minbound[i][j]\geqslant minbound[i][k]+minbound[k][j]$ ，发现这个和 $\text{floyed}$ 的式子很像，于是可以用 $\text{floyed}$ 来转移它，这样就得到了每一个差值合法的上下界，然后枚举 $C$ 和 $D$ 分类讨论， $A+B\leqslant C+D\Rightarrow A-C\leqslant D-B,A-D\leqslant C-B$ ，注意这两个不等式只要有一个满足就成立。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline char getc()

{

    register char c = getchar();

    while(c != '?' && c != '+' && c != '-' && c != '=')c = getchar();

    return c;

}

int n,A,B;

#define MAXN 51

char c[MAXN][MAXN];

int maxbound[MAXN][MAXN],minbound[MAXN][MAXN];

int main()

{

    scanf("%d%d%d",&n,&A,&B);

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= n;++j)

        {

            c[i][j] = getc();

            if(c[i][j] == '=' || i == j){maxbound[i][j] = 0;minbound[i][j] = 0;}

            if(c[i][j] == '-'){maxbound[i][j] = -1;minbound[i][j] = -2;}

            if(c[i][j] == '+'){maxbound[i][j] = 2;minbound[i][j] = 1;}

            if(c[i][j] == '?'){maxbound[i][j] = 2;minbound[i][j] = -2;}

        }

    }

    for(int k = 1;k <= n;++k)

    {

        for(int i = 1;i <= n;++i)

        {

            for(int j = 1;j <= n;++j)

            {

                if(i == j || j == k || i == k)continue;

                maxbound[i][j] = min(maxbound[i][j],maxbound[i][k] + maxbound[k][j]);

                minbound[i][j] = max(minbound[i][j],minbound[i][k] + minbound[k][j]);

            }

        }

    }

    int ans1 = 0,ans2 = 0,ans3 = 0;

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j < i;++j)

        {

            if(i == A || i == B || j == A || j == B)continue;

            if(minbound[A][i] > maxbound[j][B] || minbound[A][j] > maxbound[i][B])

            {

                ++ans1;continue;

            }

            if(

            (minbound[A][i] == maxbound[A][i] && maxbound[A][i] == minbound[j][B] && minbound[j][B] == maxbound[j][B]) || 

            (minbound[A][j] == maxbound[A][j] && maxbound[A][j] == minbound[i][B] && minbound[i][B] == maxbound[i][B])

            )

            {

                ++ans2;continue;

            }

            if(maxbound[A][i] < minbound[j][B] || maxbound[A][j] < minbound[i][B])

            {

                ++ans3;continue;

            }

        }

    }

    cout << ans1 << " " << ans2 << " " << ans3 << endl;

    return 0;

}