P2474 题解

前言

题目传送门！

更好的阅读体验？

差分约束。

思路

预处理

维护两个数组 \(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 就可以了。

转移：

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

完整代码

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

#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;
}

希望能帮助到大家！