洛谷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;
}