差分约束

定义

差分约束系统 是一种特殊的\(n\)元一次不等式组，它包含\(n\)个变量\(x_1,x_2,\dots,x_n\) 以及\(m\)个约束条件，每个约束条件是由两个其中的变量做差构成的,形如\(x_i-x_j≤C_k\)或者\(x_i-x_j≥C_k\)其中\(1≤i,j≤n，1≤k≤m\)

做法

假如有式子

我们发现由前两个式子相加可以得到\(x_1-x_3≤C_1+C_2\)，和第三个式子对比发现，如果要满足这三个式子，那么\(x_1-x_3\)应该在\(C_1+C_2\)和\(C_3\)中取一个最小值，那么此时就会发现这个结构跟最短路的三角形不等式相似，如果将作差比作一条路径的话那么就是\(dis[1][2]+dis[2][3]\)跟\(dis[1][3]\)取\(min\),同理\(x_i-x_j≥C_k\)的时候应该取\(max\)

那么定义\(fmax[i][j]\)为\(x_i-x_j\)的最大值，\(fmin[i][j]\)为\(x_i-x_j\)的最小值，当\(x_i-x_j≤C_k\)可以给\(fmax[i][j]\)赋值为\(C_k\)，当\(x_i-x_j≥C_k\)给\(fmin[i][j]\)赋值为\(C_k\)，但是更新的时候要给\(fmax\)取\(min\)，给\(fmin\)取\(max\)，原理就是上面的式子

知道了原理之后，剩下的就是跑最短路/最长路了

例题洛谷P2474

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,A,B;
char s[55];
int fmin[55][55],fmax[55][55];
int main()
{
	memset(fmax,127,sizeof(fmax));
	scanf("%d%d%d",&n,&A,&B);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		int l = strlen(s+1);
		for(int j=1;j<=l;j++)
		{
			if(s[j] == '=' || i == j)
			{
				fmin[i][j] = fmax[i][j] = 0;
			}
			else if(s[j] == '+')
			{
				fmin[i][j] = 1;
				fmax[i][j] = 2;
			}
			else if(s[j] == '-')
			{
				fmin[i][j] = -2;
				fmax[i][j] = -1;
			}
			else if(s[j] == '?')
			{
				fmin[i][j] = -2;
				fmax[i][j] = 2;
			}
		}
		getchar();
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				fmin[i][j] = max(fmin[i][j],fmin[i][k]+fmin[k][j]);
				fmax[i][j] = min(fmax[i][j],fmax[i][k]+fmax[k][j]);
			}
	int c1 = 0,c2 = 0,c3 = 0;
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
		{
			if(A == i || A == j || B == i || B == j) continue;
			if(fmax[A][i] < fmin[j][B] || fmax[A][j] < fmin[i][B]) c3 ++;
			else if(fmax[A][i] == fmin[A][i] && fmax[j][B] == fmin[j][B] && fmax[A][i] == fmax[j][B]) c2 ++;
			else if(fmax[A][j] == fmin[A][j] && fmax[i][B] == fmin[i][B] && fmax[A][j] == fmax[i][B]) c2 ++;
			else if(fmin[A][i] > fmax[j][B] || fmin[A][j] > fmax[i][B]) c1 ++;
		}
	printf("%d %d %d",c1,c2,c3);
	return 0;
}