题目描述
你有n个砝码，均为1克，2克或者3克。你并不清楚每个砝码的重量，但你知道其中一些砝码重量的大小关系。你把其中两个砝码A 和B 放在天平的左边，需要另外选出两个砝码放在天平的右边。问：有多少种选法使得天平的左边重(c1)、一样重(c2)、右边重(c3)？（只有结果保证惟一的选法才统计在内）
输入输出格式
输入格式：
第一行包含三个正整数n，A，B（1<=A，B<=N，A 和B 不相等）。砝码编号
为1~N。以下n行包含重量关系矩阵，其中第i行第j个字符为加号“+”表示砝
码i比砝码j重，减号“-”表示砝码i比砝码j 轻，等号“=”表示砝码i和砝码
j一样重，问号“?”表示二者的关系未知。存在一种情况符合该矩阵。
输出格式：
仅一行，包含三个整数，即c1，c2和c3。
输入输出样例
输入样例#1：
6 2 5?+????-?+????-????????+????-?+????-?
输出样例#1：
1 4 1
输入样例#2：
14 8 4?+???++?????++-??=?=???????=??????????=????=??+?==?????????-???-???-??-=????????????-??=???=?-+??????=+?=???????????????????????????+?????????=???-????-??????+?????+???-?????????????-=????????????
输出样例#2：
18 12 11
说明
4<=n<=50
这道题n这么小一看就是乱搞的数据范围嘛...
这道题因为有很多不确定的关系 所以考虑用差分约束做这道题
我们维护两个数组$dx[i][j], dn[i][j]$分别表示$w[i] - w[j]$的可能最大值与可能最小值
换句话说$w[i] - w[j] <= dx[i][j], w[i] - w[j] >= dn[i][j]$ 然后使用弗洛伊德跑一边最短 最长路
相当于收缩边界 这个会差分约束还是很好懂的 然后对于关系一定确定的统计答案即可
代码
#includeusing namespace std;const int N = 100 + 5;int dn[N][N], dx[N][N], n, a, b;char s[N];void Init( ) { scanf("%d%d%d",& n,& a,& b); for(int i = 1;i <= n;i ++) { scanf("%s", s + 1); for(int j = 1;j <= n;j ++) { if(s[j] == '=' || i == j) dx[i][j] = dn[i][j] = 0; else if(s[j] == '-') { dx[i][j] = -1, dn[i][j] = -2; } else if(s[j] == '+') { dx[i][j] = 2, dn[i][j] = 1; } else dx[i][j] = 2, dn[i][j] = -2; } }}void Solve( ) { for(int k = 1;k <= n;k ++) { for(int i = 1;i <= n;i ++) { if(i == k) continue; for(int j = 1;j <= n;j ++) { if(i == j) continue; dx[i][j] = min(dx[i][k] + dx[k][j], dx[i][j]); dn[i][j] = max(dn[i][k] + dn[k][j], dn[i][j]); } } } int num1 = 0, num2 = 0, num3 = 0; for(int i = 1;i <= n;i ++) { if(i == a || i == b) continue; for(int j = 1;j < i;j ++) { if(j == i || j == a || j == b) continue; if(dn[a][i] > dx[j][b] || dn[a][j] > dx[i][b]) num1 ++; if(dn[j][b] > dx[a][i] || dn[i][b] > dx[a][j]) num2 ++; if((dn[a][i] == dx[a][i] && dn[j][b] == dx[j][b] && dn[a][i] == dn[j][b]) || (dn[a][j] == dx[a][j] && dn[i][b] == dx[i][b] && dn[a][j] == dn[i][b])) num3 ++; } } printf("%d %d %d ", num1, num3, num2);}int main( ) { Init( ); Solve( );}