自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 21:38:07，当前版本为作者最后更新于2022-11-10 08:45:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题目传送门！

更好的阅读体验？

差分约束。

update：修改了 $\LaTeX$，这下应该正常了。

思路

预处理

维护两个数组 $mn_{i, j}$ 与 $mx_{i, j}$，表示砝码 $i$ 与砝码 $j$ 重量差值的最小最大。

我们分类讨论：

1. $i = j$，显然 $mx = mn = 0$。
2. $a_{i, j}$ 为 =，$mx = mn = 0$，因为关系已经固定。
3. $a_{i, j}$ 为 +，差值最大：$a_i=3$，$a_j=1$。最小：$a_i=2$，$a_j=1$。所以 $mx = 2, mn = 1$。
4. $a_{i, j}$ 为 -，与上面反过来，$mx = -1, mn = -2$。
5. $a_{i, j}$ 为 ?，差值最大：$a_i=3$，$a_j=1$。最小反过来。所以 $mx = 2, mn = -2$。

差分约束

统计完基本信息后，就可以差分约束了。

由于数据范围很小（$n \le 50$），并且统计答案时需要全局统计，所以用 Floyd 就可以了。

转移：（$1 \le k \le n$）

$\begin{cases}mx_{i, j} = \min\{mx_{i, k} + mx_{k, j}\}\\ mn_{i, j} = \max\{mn_{i, k} + mn_{k, j}\}\end{cases}$

反向取上下界，应该很容易理解吧。

统计答案

对于所有 $i \ne A$ 且 $j \ne B$ 且 $i \ne j$ 的两个砝码 $i, j$，统计答案。

同样是分类讨论：

1. 如果 $mn_{A, i} > mx_{j, B}$ 或者 $mn_{A, j} > mx_{i, B}$，说明左边有可能重。

2. 如果 $mn_{A, i} = mx_{A, i} = mn_{j, B} = mx_{j, B}$，说明有可能相等； 同理，如果 $mn_{B, i} = mx_{B, i} = mn_{j, A} = mx_{j, A}$，也有可能相等；

3. 与左边重的情况相反，如果 $mn_{A, i} < mx_{j, B}$ 或者 $mn_{A, j} < mx_{i, B}$，说明右边有可能重。

统计好后输出即可。这道题就完美的做完啦！

完整代码

略微压行，凑合着看看吧，应该很容易看懂。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 55;
int n, A, B;
int maxd[N][N], mind[N][N]; //maxd[i][j] 或 mind[i][j] 表示：砝码 i 与砝码 j 重量差值 的最值。 
void Input()
{
	scanf("%d%d%d", &n, &A, &B);
	for  (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			char x;
			cin >> x;
			if (i == j || x == '=') maxd[i][j] = mind[i][j] = 0; //别忘了：同一块砝码，最值都是 0。 
			else if (x == '+') maxd[i][j] = 2, mind[i][j] = 1; //差值最大：a[i]=3，a[j]=1。最小：a[i]=2，a[j]=1。 
			else if (x == '-') maxd[i][j] = -1, mind[i][j] = -2; //恰好与上面反过来。
			else if (x == '?') maxd[i][j] = 2, mind[i][j] = -2; //差值最大：a[i]=3，a[j]=1。最小：a[i]=1，a[j]=3。
		}
}
void Floyd() //差分约束
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				maxd[i][j] = min(maxd[i][j], maxd[i][k] + maxd[k][j]),
				mind[i][j] = max(mind[i][j], mind[i][k] + mind[k][j]);
}
void Output()
{
	int lcnt = 0, ecnt = 0, rcnt = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
		{
			//要保证 i 与 j 均不是给定砝码。 
			if (i == A || i == B) break;
			if (j == A || j == B) continue;
			if (mind[A][i] > maxd[j][B] || mind[A][j] > maxd[i][B]) lcnt++;
			
			if (mind[A][i] == maxd[A][i] && mind[A][i] == mind[j][B] && mind[j][B] == maxd[j][B]) ecnt++;
			else if (mind[B][i] == maxd[B][i] && mind[B][i] == mind[j][A] && mind[j][A] == maxd[j][A]) ecnt++;
			
			if (maxd[A][i] < mind[j][B] || maxd[A][j] < mind[i][B]) rcnt++;
		}
	printf("%d %d %d", lcnt, ecnt, rcnt);
}
int main()
{
	//程序三段式，十分清晰美观。 
	Input();
	Floyd();
	Output();
	return 0;
}

希望能帮助到大家！