(几万年前的博客了,刚从洛谷搬过来)
主要内容
差分约束系统 是一种特殊的 \(n\) 元一次不等式组 。
差分约束系统中的每个约束条件 \(x_i-x_j\le c_k\) 都可以变形成 \(x_i\le x_j+c_k\) 与 \(x_j\ge x_i-c_k\) ,这与单源最短路中的三角形不等式非常相似。因此,我们可以把每个变量 \(x_i\) 看做图中的一个结点,对于每个约束条件连边。
需要注意的是,有些题目看能会对解的上、下界进行约束,因此我们需要对这些条件处理(这里只考虑对于这 \(n\) 个元素 只约束了上界 或 只约束了下界 ):
-
只约束下界:有 \(0\) 号点向每一个点连一条长为 \(Lim_i\) 的边,表示第 \(i\) 号元素的 下界 为 \(Lim_i\) ,如图所示建边:
题意 转化 连边 \(x_a-x_b\ge c\) \(x_a\ge x_b+c\) add(b,a,c)
\(x_a-x_b\le c\) \(x_b\ge x_a-c\) add(a,b,-c)
\(x_a=x_b\) \(x_a\ge x_b\) , \(x_b\le x_a\) add(a,b,0),add(b,a,0)
之后对整张图跑 最长路 。
-
只约束上界:有 \(0\) 号点向每一个点连一条长为 \(Lim_i\) 的边,表示第 \(i\) 号元素的 上界 为 \(Lim_i\) ,如图所示建边:
题意 转化 连边 \(x_a-x_b\ge c\) \(x_b\le x_a-c\) add(a,b,-c)
\(x_a-x_b\le c\) \(x_a\le x_b+c\) add(b,a,c)
\(x_a=x_b\) \(x_a\le x_b\) , \(x_b\le x_a\) add(a,b,0),add(b,a,0)
之后对整张图跑 最短路 。
设 \(dist[0]=0\) ,若存在负环 \(/\) 正环,则不等式无解,否则 \(x_i=dist[i]\) 是该差分约束系统的一组解 。
最坏情况下(存在负环 \(/\) 正环)复杂度为 \(O(nm)\) 。
注意:整个图不一定是联通的!
例题
P1993 小 K 的农场 - 模板
P2474 [SCOI2008]天平
$\texttt{solution}$
用 \(mi[i][j]\) 和 \(mx[i][j]\) 表示 \(i\) 和 \(j\) 号砝码的质量差的最大值 \(/\) 最小值 这道题由于数据范围小,可以用 \(\operatorname{Floyd}\) 算法跑最短路 \(/\) 最长路。判断天平平衡情况可以如下讨论:
-
\(a+b>i+j\) ,天平左倾,满足 \(a-i>j-b\) :
\(min[a][i]>max[j][b]\)
-
\(a+b=i+j\) ,天平平衡,满足 \(a-i=j-b\) :
\(min[a][i]=max[a][i]~\&~min[j][b]=max[j][b]~\&~min[a][i]=min[j][b]\)
-
\(a+b<i+j\) ,天平右倾,满足 \(a-i<j-b\) :
\(max[a][i]<min[j][b]\)
核心代码:
n=rd(),a=rd(),b=rd();
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
cin>>c;
if(c=='+') mi[i][j]=1,mx[i][j]=2;
else if(c=='-') mi[i][j]=-2,mx[i][j]=-1;
else if(c=='=' || i==j) mi[i][j]=mx[i][j]=0;
else mi[i][j]=-2,mx[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 && j!=k && i!=j)
mi[i][j]=max(mi[i][j],mi[i][k]+mi[k][j]),mx[i][j]=min(mx[i][j],mx[i][k]+mx[k][j]);
for(int i=1;i<=n;i++) if(i!=a && i!=b)
for(int j=1;j<i;j++) if(j!=a && j!=b)
{
if(mi[a][j]>mx[i][b] || mi[a][i]>mx[j][b]) c1++;
if((mi[a][i]==mi[j][b] && mi[a][i]==mx[a][i] && mi[j][b]==mx[j][b]) || (mi[a][j]==mi[i][b] && mi[a][j]==mx[a][j] && mi[i][b]==mx[i][b])) c2++;
if(mx[a][j]<mi[i][b] || mx[a][i]<mi[j][b]) c3++;
}
printf("%d %d %d\n",c1,c2,c3);
P4926 [1007]倍杀测量者
$\texttt{solution}$
给出一系列不等式:
\[x_{a_i}\ge (k_i-t)\times x_{b_i}~~~\&~~~(k_i+t)\times x_{a_i}>x_{b_i} \]以及一些 \(x_i\) 的值 。
求出最大的 \(t\) 使得不等式无解 。
1. 连边
首先对不等式进行拆分化简:
连边 add(b,a,log2(k-t))
由于本题有精度 \(10^{-5}\) 的容量范围,所以我们可以连边 add(b,a,-log2(k+t))
(具体实现连边操作时只用记录 \(k\) 的值,\(t\) 根据边的种类在差分的时候分类讨论。)
2. 判断无解
输出 -1
仅当 \(t=0\) 时不等式仍旧有解 。
3. 二分答案
二分一个 \(t\) ,判断这个时候不等式是否有解 。输出答案 。
上AC代码(去掉了不必要的部分):
#define inf 0x7f7f7f7f
#define Maxn 5005
int n,s,t,tot;
int cnt[Maxn],hea[Maxn],nex[Maxn*2],ver[Maxn*2],typ[Maxn*2];
double ds[Maxn],edg[Maxn*2];
bool inq[Maxn];
inline void add(int x,int y,double d,int Type)
{
ver[++tot]=y,edg[tot]=d,typ[tot]=Type,nex[tot]=hea[x],hea[x]=tot;
}
bool spfa(double tmp) // tmp 这里表示上面说的 t 的值
{
for(int i=0;i<=n;i++) ds[i]=-inf,cnt[i]=0,inq[i]=false; ds[n+1]=0;
queue<int> q; q.push(n+1),inq[n+1]=true;
while(!q.empty())
{
int cur=q.front(); q.pop(),inq[cur]=false;
for(int i=hea[cur];i;i=nex[i])
{
double w=edg[i]; // 类型为 3 的边
if(typ[i]==1) w=log2(edg[i]-tmp); // 类型为 1 的边
if(typ[i]==2) w=-log2(edg[i]+tmp); // 类型为 2 的边
if(ds[ver[i]]<ds[cur]+w)
{
ds[ver[i]]=ds[cur]+w,cnt[ver[i]]=cnt[cur]+1;
if(cnt[ver[i]]>=n+2) return true; // 判断无解
else if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
}
}
}
return false; // 此时有解
}
double x,l=0,r=10,ans,mid;
scanf("%d%d%d",&n,&s,&t);
for(int i=0;i<=n;i++) add(n+1,i,0,3);
for(int i=1,opt,a,b;i<=s;i++)
{
scanf("%d%d%d%lf",&opt,&a,&b,&x),add(b,a,x,opt);
if(opt==1) r=fmin(r,x);
}
for(int i=1,c;i<=t;i++) scanf("%d%lf",&c,&x),add(0,c,log2(x),3),add(c,0,-log2(x),3);
if(!spfa(0)) printf("-1\n");
else
{
while(r-l>cha) // cha 是 0.00001 保证精度
{
mid=(l+r)/2.0;
if(spfa(mid)) ans=mid,l=mid+cha;
else r=mid-cha;
}
printf("%.6lf\n",ans);
}
P5590 赛车游戏
首先到达一个点的每一条路径长度一定相同,记为 \(s_x\)。
有点和边的限制,那么考虑将“到个点的长度和一条边的权值”设为一个整体进行差分约束,记作 \(p_x\)。
那么对于到达同一个终点的一对点来说,\(s_x+e_i=s_y+e_j\),即 \(p_i=p_j\)。
还有一个重要限制是 \(e_i\in[1,9]\),即 \(a\rightarrow b\rightarrow c\) 的一条路径可以表示为:\(p_a+9\ge p_b,p_a+1\le p_b\),之后似乎直接差分约束就好了。
这道题需要注意的是:应当先除去不在 \(1\) 到 \(n\) 路径上的点,它们会影响答案的限制。