差分约束
定义
差分约束系统 是一种特殊的\(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\)
做法
假如有式子
\[\left\{\begin{matrix} x_1-x_2≤C_1 \\ x_2-x_3≤C_2 \\ x_1-x_3≤C_3 \end{matrix}\right.\]我们发现由前两个式子相加可以得到\(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;
}
标签:fmax,差分,约束,55,int,fmin,式子
From: https://www.cnblogs.com/-Wind-/p/18307583