差分约束系统

• $A+B>C+D$

也就是 $A-C>D-B$ 或者 $A-D>C-B$ ，即 $\min(A-D)>\max(C-B)$ 或者 $\min(A-C)>\max(D-B)$ .

• $A+B=C+D$

$A-C=D-B$ 或者 $A-D=C-B$ . 所以有：

$\min(A-C)=\max(A-C)=\min(D-B)=\max(D-B)$ 或者 $\min(A-D)=\max(A-D)=\min(C-B)=\max(C-B)$ .

• $A+B>C+D$

$A-C<D-B$ 或者 $A-D<C-B$ . 即 $\max(A-C)<\min(D-B)$ 或者 $\max(A-D)<\max(C-B)$ .

求出两两砝码重量差的最大最小值，然后 Floyd 差分约束即可。

//Author: AutomaticLove
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
void bmax( int &a,int b ) { a=(a>b) ? a : b; }
void bmin( int &a,int b ) { a=(a<b) ? a : b; }
int read()
{
    int x=0,w=1; char ch=getchar();
    while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
    while ( ch<='9' && ch>='0' ) x=x*10+ch-'0',ch=getchar();
    return x*w;
}

const int N=55;
int n,A,B,mx[N][N],mn[N][N];
char s[N];

int main()
{
    scanf( "%d%d%d",&n,&A,&B);
    for ( int i=1; i<=n; i++ )
    {
        scanf( "%s",s+1 );
        for ( int j=1; j<=n; j++ ) 
            if ( s[j]=='+' ) mx[i][j]=2,mn[i][j]=1;
            else if ( s[j]=='-' ) mx[i][j]=-1,mn[i][j]=-2;
            else if ( s[j]=='=' || i==j ) mx[i][j]=0,mn[i][j]=0;
            else if ( s[j]=='?' ) mx[i][j]=2,mn[i][j]=-2;
    }

    for ( int k=1; k<=n; k++ )
        for ( int i=1; i<=n; i++ ) if ( i^k )
            for ( int j=1; j<=n; j++ ) if ( (i^j) && (j^k) )
                bmin(mx[i][j],mx[i][k]+mx[k][j]),
                bmax(mn[i][j],mn[i][k]+mn[k][j]);

    int c1=0,c2=0,c3=0;
    for ( int C=1; C<=n; C++ )
        for ( int D=1; D<C; D++ )
            if ( (C^A) && (C^B) && (D^A) && (D^B) )
            {
                if ( mn[A][C]>mx[D][B] || mn[A][D]>mx[C][B] ) c1++;
                if ( (mn[A][C]==mx[A][C] && mn[D][B]==mx[D][B] && mn[A][C]==mx[D][B])
                    || (mn[A][D]==mx[A][D] && mn[C][B]==mx[C][B] && mn[A][D]==mx[C][B]) ) c2++;
                if ( mx[A][C]<mn[D][B] || mx[A][D]<mn[C][B] ) c3++;
            }

    printf("%d %d %d\n",c1,c2,c3 );

    return 0;
}