[SCOI2008]天平

LZDQ · 2021-12-06 19:26:32 · 题解

题解都是差分约束，不过这题有一个更好想的暴力。

首先我们把相等的点用并查集缩起来，缩完点之后建一张有向图，边表示大于的关系。不难发现如果有一条三个点的链，那么这三个点的取值是确定的。如果一个点不在这样的链上并且有入边，那么单看这个点的取值可以是 1 或 2。如果有出边，那么取值可以是 2 或 3。所以如果单看一个点可以 \Theta(n^3) 预处理出这个点取值的区间。

枚举另外两个点 c,d 以及 a,b,c,d 这四个点的取值，除了单看一个点的取值范围限制，还要考虑这四个点之间互相影响的情况。判完两两之间的合法性后，实际上就可以了，三个点是不会互相影响的，因为三个点互相影响必须要连成一条链，而这样一条链在取值范围已经被限死了。

复杂度 \Theta(n^3+3^4n^2)。

够暴力了吧。

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int MAXN=55;
int n,a,b;
char s[MAXN][MAXN];
int pre[MAXN];
int fnd(int x){
    if(x!=pre[x]) pre[x]=fnd(pre[x]);
    return pre[x];
}
int rg[MAXN][2];
int ans[3];
int p[5],v[5];
int Check(){
    for(int i=1; i<=4; i++)
        for(int j=1; j<=4; j++){
            int x=p[i],y=p[j];
            if(s[x][y]=='='&&v[i]!=v[j]) return 0;
            if(s[x][y]=='+'&&v[i]<=v[j]) return 0;
        }
    return 1;
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1; i<=n; i++)
        scanf("%s",s[i]+1),pre[i]=i,rg[i][0]=1,rg[i][1]=3,s[i][i]='=';
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(s[i][j]=='=') pre[fnd(i)]=fnd(j);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
            int x=fnd(i),y=fnd(j);
            if(s[i][j]=='+') s[x][y]='+',s[y][x]='-';
            if(s[i][j]=='-') s[x][y]='-',s[y][x]='+';
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
            int x=fnd(i),y=fnd(j);
            if(s[x][y]=='+'){
                rg[x][0]=2,rg[x][1]=3;
                rg[y][0]=1,rg[y][1]=2;
            }
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++){
                int x=fnd(i),y=fnd(j),z=fnd(k);
                if(s[x][y]=='+'&&s[y][z]=='+'){
                    rg[x][0]=rg[x][1]=3;
                    rg[y][0]=rg[y][1]=2;
                    rg[z][0]=rg[z][1]=1;
                }
            }
    for(int i=1; i<=n; i++){
        if(i==a||i==b) continue;
        for(int j=i+1; j<=n; j++){
            if(j==a||j==b) continue;
            int c=fnd(i),d=fnd(j);
#define a fnd(a)
#define b fnd(b)
            p[1]=a;
            p[2]=b;
            p[3]=c;
            p[4]=d;
            int cnt[3]={0,0,0};
            for(v[1]=rg[a][0]; v[1]<=rg[a][1]; v[1]++)
                for(v[2]=rg[b][0]; v[2]<=rg[b][1]; v[2]++)
                    for(v[3]=rg[c][0]; v[3]<=rg[c][1]; v[3]++)
                        for(v[4]=rg[d][0]; v[4]<=rg[d][1]; v[4]++)
                            cnt[(v[1]+v[2]>v[3]+v[4])+(v[1]+v[2]>=v[3]+v[4])]|=Check();
            if(cnt[0]+cnt[1]+cnt[2]==1){
                ans[0]+=cnt[0];
                ans[1]+=cnt[1];
                ans[2]+=cnt[2];
            }
        }
    }
    printf("%d %d %d\n",ans[2],ans[1],ans[0]);
    return 0;
}