P2474-[SCOI2008]天平
题目:
题目描述:
你有 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:
1
2
3
4
5
6
7
| 6 2 5
?+????
-?+???
?-????
????+?
???-?+
????-?
|
样例输出 1:
样例输入 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 14 8 4
?+???++?????++
-??=?=???????=
??????????=???
?=??+?==??????
???-???-???-??
-=????????????
-??=???=?-+???
???=+?=???????
??????????????
??????+???????
??=???-????-??
????+?????+???
-?????????????
-=????????????
|
样例输出 2:
思路:
实现:
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
58
59
60
61
62
63
64
65
66
67
68
| #include "ybwhead/ios.h"
int n, a, b;
const int mxxn = 1e3 + 10;
int mx[mxxn][mxxn];
int mi[mxxn][mxxn];
int main()
{
yin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
char c;
yin >> c;
if (c == '=' || i == j)
{
continue;
}
if (c == '-')
{
mx[i][j] = -1;
mi[i][j] = -2;
}
if (c == '+')
{
mx[i][j] = 2;
mi[i][j] = 1;
}
if (c == '?')
{
mx[i][j] = 2;
mi[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 && j != k)
mx[i][j] = min(mx[i][j], mx[i][k] + mx[k][j]),
mi[i][j] = max(mi[i][j], mi[i][k] + mi[k][j]);
int tmp1, tmp2, tmp3;
tmp1 = tmp2 = tmp3 = 0;
for (int i = 1; i <= n; i++)
{
if (i != a && i != b)
{
for (int j = 1; j < i; j++)
{
if (j == a || j == b)
continue;
if (mi[a][i] > mx[j][b] || mi[b][i] > mx[j][a])
++tmp1;
if (mi[a][i] == mx[a][i] && mi[a][i] == mx[j][b] && mx[j][b] == mi[j][b])
{
++tmp2;
continue;
}
if (mi[a][j] == mx[a][j] && mi[a][j] == mi[i][b] && mi[i][b] == mx[i][b])
++tmp2;
if (mi[i][a] > mx[b][j] || mi[i][b] > mx[a][j])
++tmp3;
}
}
}
yout << tmp1 << ' ' << tmp2 << " " << tmp3 << endl;
return 0;
}
|