题解 P2474 【[SCOI2008]天平】

Hexarhy · 2020-10-07 21:10:20 · 题解

Preface

差分约束进阶题，有助于加深印象，也避免了对模板的固化。

刚开始写了 SPFA 后来发现不如 Floyd 方便就重构代码了……

Solution

题目有 3 个问题，不妨先对 A+B>C+D 进行思考。

原不等式等价于 A-C>D-B 或 A-D>C-B。显然，数据量允许我们暴力枚举 C,D 判断是否成立。

传统的差分约束是直接求出一组解。但这里直接的搭配的解不唯一很不方便，我们尝试维护变量间的和差关系以直接满足不等关系。

此时，我们就可以设 f(u,v) 为 u,v 的 \max\{u-v\}，g(u,v)=\min\{u-v\}。u-v\le f(u,v) 或 u-v\ge g(u,v) 相当于从 v 出发到 u 的最短/长路。而暴力枚举 C,D 就要求我们跑全源最短路。

即，跑两次 Floyd，一次跑最短路得到 f(u,v)，一次跑最长路得到 g(u,v)。

用邻接矩阵建图的时候，

对于+，i>j，即 i-j>0，可以得到 i-j=1 或 i-j=2，于是就有 f(i,j)=2,g(i,j)=1。
对于-，有 i-j=-1 或 i-j=-2，即 f(i,j)=-1,g(i,j)=-2。
对于=，有 i=j，即 f(i,j)=g(i,j)=0。
对于?，i,j 关系未知，就假设两种最极端的情况，把 f(i,j)=2,g(i,j)=-2。

接下来就是如何判断不等关系成立。

对于 A-C>D-B，显然为了使结果唯一，必须使得 g(A,C)>f(D,B)，即前者的最小值都已经比后者的最大值还要大，那么结果肯定是唯一的左边大于右边。

同理，对于 A-D>C-B，就要使得 g(A,D)>f(D,B)。两个条件显然只要满足一个即可，用逻辑或连接。

将上述做法推广到 3 个问题即可。

对于 A+B=C+D，等价于 A-D=C-B 或 A-C=D-B，即 f(A,D)=g(C,B)=g(A,D)=f(C,B) 或 f(A,C)=g(D,B)=g(A,C)=f(D,B)。
对于 A+B<C+D，等价于 A-C<D-B 或 A-D<C-B，即 f(A,C)<g(D,B) 或 f(A,D)<g(C,B)。

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

Notice

由于我们要对多个问进行统计答案，于是可以写个函数来多次调用，传参的时候给一个 lambda 表达式来当作比较函数即可。可以减少码量并方便调试。需要C++11。

其余的只是代码繁琐而已，细心就行。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef const int cint;
cint MAXN=55;
int n,A,B;
int minn[MAXN][MAXN],maxx[MAXN][MAXN];

template<typename Comp>
void floyd(int dis[MAXN][MAXN],const Comp func)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=k && k!=j && i!=j)
                    dis[i][j]=func(dis[i][j],dis[i][k]+dis[k][j]);
}

template<typename Comp>
void solve(const Comp cmp)
{
    int ans=0;
    for(int i=1;i<=n;i++)
        if(i!=A && i!=B)
            for(int j=i+1;j<=n;j++)
                if(j!=A && j!=B)
                    if(cmp(A,B,i,j))
                        ans++;
    cout<<ans<<' ';
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            char ch;cin>>ch;
            if(ch=='+')
            {
                maxx[i][j]=2;
                minn[i][j]=1;
            }
            if(ch=='-')
            {
                maxx[i][j]=-1;
                minn[i][j]=-2;
            }
            if(ch=='?')
            {
                maxx[i][j]=2;
                minn[i][j]=-2;
            }
        }
    floyd(maxx,[&](cint a,cint b){return a<b?a:b;});
    floyd(minn,[&](cint a,cint b){return a>b?a:b;});
    solve([&](cint a,cint b,cint c,cint d)
    {
        return minn[a][c]>maxx[d][b] || minn[a][d]>maxx[c][b];
    });
    solve([&](cint a,cint b,cint c,cint d)
    {
        return (minn[a][c]==maxx[d][b] && maxx[a][c]==minn[d][b] && minn[d][b]==maxx[d][b])
            || (minn[a][d]==maxx[c][b] && maxx[a][d]==minn[c][b] && minn[c][b]==maxx[c][b]);
    });
    solve([&](cint a,cint b,cint c,cint d)
    {
        return maxx[a][c]<minn[d][b] || maxx[a][d]<minn[c][b];
    });
    cout<<endl;
    return 0;
}