1077: [SCOI2008]天平

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 475  Solved: 260

[][][]

Description

　　你有n个砝码，均为1克，2克或者3克。你并不清楚每个砝码的重量，但你知道其中一些砝码重量的大小关系。你把其中两个砝码A和B放在天平的左边，需要另外选出两个砝码放在天平的右边。问：有多少种选法使得天平的左边重(c1)、一样重(c2)、右边重(c3)？（只有结果保证惟一的选法才统计在内)

Input

　　第一行包含三个正整数n，A，B（1<=A，B<=N，A和B不相等）。砝码编号为1~N。以下n行包含重量关系矩阵，其中第i行第j个字符为加号“+”表示砝码i比砝码j重，减号“-”表示砝码i比砝码j轻，等号“=”表示砝码i和砝

码j一样重，问号“?”表示二者的关系未知。存在一种情况符合该矩阵

Output

　　仅一行，包含三个整数，即c1，c2和c3。

Sample Input

6 2 5

?+????

-?+???

?-????

????+?

???-?+

????-?

Sample Output

1 4 1

HINT

【数据规模】 4<=n<=50

题解

mn[i][j]表示a[i]-a[j]的最小值，mx[i][j]表示a[i]-a[j]的最大值，跑floyd缩小范围。

再暴力枚举判断关系即可。

代码

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=55;int n,a,b,c1,c2,c3;int mn[N][N],mx[N][N];int main(){	scanf("%d%d%d",&n,&a,&b);	char s[N];	for(int i=1;i<=n;i++){		scanf("%s",s+1);		for(int j=1;j<=n;j++){			if(s[j]=='+'){				mn[i][j]=1;				mx[i][j]=2;			}			else if(s[j]=='-'){				mn[i][j]=-2;				mx[i][j]=-1;			}			else if(s[j]=='='){				mn[i][j]=0;				mx[i][j]=0;			}			else{				mn[i][j]=-2;				mx[i][j]=2;			}		}		mn[i][i]=0;		mx[i][i]=0;	}	for(int k=1;k<=n;k++){		for(int i=1;i<=n;i++){			for(int j=1;j<=n;j++){				if(i==j||i==k||j==k)continue;				mn[i][j]=max(mn[i][j],mn[i][k]+mn[k][j]);				mx[i][j]=min(mx[i][j],mx[i][k]+mx[k][j]);			}		}	}	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;			if(mn[a][i]>mx[j][b]||mn[a][j]>mx[i][b])c1++;			if((mn[a][i]==mx[a][i]&&mn[b][j]==mx[b][j]&&mn[a][i]==-mx[b][j])||(mn[a][j]==mx[a][j]&&mn[b][i]==mx[b][i]&&mn[a][j]==-mx[b][i]))c2++;			if(mx[a][i]