洛谷P2474 [SCOI2008]天平题解

题目链接：P2474 [SCOI2008]天平

题意：

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

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

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

输入格式：

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

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

输出格式：

输出一行，包含三个整数，即 $c_1,c_2,c_3$。

$n$ 很小，考虑枚举无序对 $(i,j)$

因此我们就是要找有多少对这样的 $(i,j)$ 使得

$w_A + w_B > w_i + w_j$

$<$ 和 $=$ 同理。

这个式子不是很好处理，于是移项，得

$w_A - w_i > w_j -w_B$

根据~~小学数学~~可知

$(w_A - w_i)_{\min} > (w_j - w_B)_{\max}$

于是考虑求出这两个东西

显然如果 $A$ 和 $i$ 直接相连，那我们在读入的时候就可以判断

毕竟 $w_i \le 3$ 也好处理，后面的 $B$ 也是同理

如果不是直接相连，相信你也想到了，$\mathtt{Floyd}$ 。

然后我们求一个最长路和最短路就好了

判断稍微长一些，其他都不难

时间复杂度 $O(n^3)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(65))

char s[N];
int n,s1,s2,c1,c2,c3;
int dx[N][N],dn[N][N];
void up(int &x,int y) { x < y ? x = y : 0;}
void down(int &x,int y) { x > y ? x = y : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> s1 >> s2;
    for(int i=1,l; i<=n; i++)
    {
        cin >> (s+1); l=strlen(s+1);
        for(int j=1; j<=l; j++)
            if(s[j]=='=' || i==j) dx[i][j]=dn[i][j]=0;
            else if(s[j] == '+') dx[i][j]=2,dn[i][j]=1;
            else if(s[j] == '-') dx[i][j]=-1,dn[i][j]=-2;
            else dx[i][j]=2,dn[i][j]=-2;
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                down(dx[i][j],dx[i][k]+dx[k][j]),
                up(dn[i][j],dn[i][k]+dn[k][j]);
                
    for(int i=1; i<=n; i++) if(i!=s1 && i!=s2)
        for(int j=1; j<i; j++) if(j!=s1 && j!=s2)
        {
            // s1-i min > j-s2 max => s1+s2 > i+j
            if(dn[s1][i] > dx[j][s2] || dn[s2][i] > dx[j][s1]) ++c1;
            // i-s1 min > s2-j max =? i+j > s1+s2
            if(dn[i][s1] > dx[s2][j] || dn[i][s2] > dx[s1][j]) ++c3;
            if((dn[s1][i]==dx[s1][i] && dn[j][s2]==dx[j][s2] && dn[s1][i]==dn[j][s2]) || 
                (dn[s1][j]==dx[s1][j] && dn[i][s2]==dx[i][s2] && dn[s1][j]==dn[i][s2])) ++c2;
        }
    cout << c1 << ' ' << c2 << ' ' << c3 << '\n';
    return 0;
}