1 条题解

  • 1
    @ 2022-9-7 12:01:37
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    int n,s1,s2;
    int dx[55][55],dn[55][55];
    int main()
    {
        scanf("%d%d%d",&n,&s1,&s2);
        char a[60];
        for(int i=1;i<=n;i++){
            scanf("%s",a);
            for(int j=0;j<strlen(a);j++){
                if(a[j]=='=' || i==j+1){
                    dn[i][j+1]=0;dx[i][j+1]=0;
                } else if(a[j]=='+') {
                    dx[i][j+1]=2;  dn[i][j+1]=1;  //i-j<=2; i-j>=1;
                }else if(a[j]=='-'){
                    dx[i][j+1]=-1; dn[i][j+1]=-2; //i-j<=-1;i-j>=-2;
                }else {
                    dx[i][j+1]=2;  dn[i][j+1]=-2; //i-j<=2; i-j>=-2;
                }
            }
        }
        
        
        for(int k=1;k<=n;k++)            //Floyd
            for(int i=1;i<=n;i++) {  
                if(i==k) continue;    
                for(int j=1;j<=n;j++){
                    if(i==k || i==j) continue;
                    dx[i][j]=min(dx[i][j],dx[i][k]+dx[k][j]);//上界求最短路
                    dn[i][j]=max(dn[i][k]+dn[k][j],dn[i][j]);//下界求最长路 
                }
            }
        
        
        int c1=0,c2=0,c3=0;
        for(int i=1;i<=n;i++){                 //暴力枚举所有可能性  
            if(i==s1 || i==s2) continue;
            for(int j=1;j<i;j++){
                if(j==s1 || j==s2) continue;
                if(dn[s1][i]>dx[j][s2] || dn[s2][i]>dx[j][s1])
                    c1++;      //s1-i的最小值大于j-s2的最大值==>s1+s2>i+j
                if(dn[i][s1]>dx[s2][j] || dn[i][s2]>dx[s1][j])
                    c3++;      //同理:i-s1>s2-j ==> i+j>s1+s2
                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++;     //关系确定且满足的点 
            }
        }
        printf("%d %d %d",c1,c2,c3);
        return 0;
    }
    
    • 1

    信息

    ID
    1422
    时间
    1000ms
    内存
    125MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者