lg2474

发表于 | 阅读数 次

链接:lg2474

题解

  • A+B<i+j ,可以转换为A-i<B-j，根据输入我们可以很容易求得i-j得上界和下界，floyd维护一下上下界，暴力枚举即可。
  • 注意上界求最短路，下界求最长路。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e3+7;
    const int inf=0x3f3f3f3f;
    int n,a,b,dx[N][N],dn[N][N],ans1,ans2,ans3;
    char str[N];
    inline void init(){
    	scanf("%d%d%d",&n,&a,&b);
    	rep(i,1,n){
    		scanf("%s",str+1);
    		rep(j,1,n){
    			if(str[j]=='=')dx[i][j]=dn[i][j]=0;
    			else if(str[j]=='+')dx[i][j]=2,dn[i][j]=1;
    			else if(str[j]=='-')dx[i][j]=-1,dn[i][j]=-2;
    			else dx[i][j]=2,dn[i][j]=-2;
    		}
    	}
    	rep(k,1,n)rep(i,1,n)if(i!=k)rep(j,1,n)if(i!=j&&j!=k){dx[i][j]=min(dx[i][j],dx[i][k]+dx[k][j]);dn[i][j]=max(dn[i][j],dn[i][k]+dn[k][j]);}
    	rep(i,1,n)rep(j,i+1,n)if(i!=a&&j!=b&&i!=b&&j!=a){
    		if(dn[a][i]>dx[j][b]||dn[a][j]>dx[i][b])ans1++;
    		if(dx[a][i]<dn[j][b]||dx[a][j]<dn[i][b])ans3++;
    		if((dn[a][i]==dx[a][i]&&dx[j][b]==dn[j][b]&&dx[a][i]==dx[j][b])||(dn[a][j]==dx[a][j]&&dx[i][b]==dn[i][b]&&dx[a][j]==dx[i][b]))ans2++;
    	}
    }
    int main(){
    	init();
    	printf("%d %d %d",ans1,ans2,ans3);
    	return 0;
    }