P2474 [SCOI2008]天平
（只有结果保证惟一的选法才统计在内）
一个棘手的问题是，我们可能不能确定两组数中每个数的大小，但是可能可以确定一组数中的和和另一组数的和的大小关系，这时考虑求两个数的差值的上下界，从而来确定答案。用 floyed 。
题中给定了 $A$ 和 $B$ ，现在判断 $C$ 和 $D$ 的和与 $A$ 和 $B$ 的和的大小关系。
如果 $A$ 比 $C$ （ $D$ ）大的下界大于了 $B$ 比 $D$ （ $C$ ）小的上界，那么一定有 $A + B > C + D$ ；反之，则 $A + B < C + D$ ；现在考虑等于的情况，$A$ 和 $B$ 是确定的，此时只有 $C$ 和 $D$ 也是确定的才可以确定，即差的上下界一定要相等。
查看代码
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <iostream>
#include <cstdio>
using namespace std;
const int N = 60;
int n, A, B, r1, r2, r3, mn[N][N], mx[N][N];
int main()
{
char c;
cin >> n >> A >> B;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> c;
if (c == '=')
{
mn[i][j] = 0;
mx[i][j] = 0;
}
else if (c == '+')
{
mn[i][j] = 1;
mx[i][j] = 2;
}
else if (c == '-')
{
mn[i][j] = -2;
mx[i][j] = -1;
}
else
{
mn[i][j] = -2;
mx[i][j] = 2;
}
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != k && i != j && k != j)
{
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++)
for (int j = 1; j < i ;j++)
if (i != A && i != B && j != A && j != B)
{
if (mn[A][i] > mx[j][B] || mn[B][i] > mx[j][A])
r1++;
else if (mn[i][A] > mx[B][j] || mn[i][B] > mx[A][j])
r3++;
else if ((mn[A][i] == mx[A][i] && mn[j][B] == mx[j][B] && mn[A][i] == mn[j][B])
|| (mn[A][j] == mx[A][j] && mn[i][B] == mx[i][B] && mn[A][j] == mn[i][B]))
r2++;
}
cout << r1 << ' ' << r2 << ' ' << r3;
return 0;
}
|