差分约束算法

---

• 参考博客差分约束算法总结

差分约束系统

如果一个系统由$n$个变量和$m$个约束条件组成，形成$m$个形如$a_i-a_j\leq k$的不等式（$i,j\in [1,n],k为常数$），则称之为差分约束系统

引例

给定$n$个变量和$m$个不等式，不等式形式为$x[i]-x[j]\leq a[k](0\leq i,j \leq n,0\eq k\leq m,a[k]已知)$，求某个$x[i]-x[j]$的最大值

例如当$n=4,m=5$，给出如下不等式组：

$$x_1-x_0\leq1（1）\\ x_2-x_0\leq2（2）\\ x_3-x_0\leq4（3）\\ x_2-x_1\leq3（4）\\ x_3-x_2\leq1（5）\\ 求max(x_3-x_0)$$

一般的解法是：把这些不等式拼拼凑凑最后得出我们要的式子，然后取一个最小值就行了，比如上例中：

$$(3)\Rightarrow x_3-x_0\leq4\\ (1)+(4)+(5)\Rightarrow x_3-x_0\leq5\\ (2)+(5)\Rightarrow x_3-x_0\leq 3\\ \Rightarrow max(x_3-x_0)=3$$

然而，谁能想到求解这个系统的过程却和我们学过的最短路算法有着密切的联系？！

与最短路的联系

我们对$x[i]-x[j]\leq a[k]$这样一个式子进行移项，得到$x[i]\leq x[j]+a[k]$，令$a[k]=w(j,i),dis[i]=x[i]=x[v],dis[j]=x[j]=x[u]$，原式变为$dis[u]+w(u,v)\geq dis[v]$，这TM不就是求最短路里的松弛操作嘛！

但好像符号反了，实际上并不矛盾，对于$x[i]-x[j]\leq a[k]$这样的不等式，我们考虑建图如下：从$j$往$i$连边，边权为$a[k]$，求$x[n-1]-x[0]$的最大值就是求$0到n-1$的最短路，两者刚好吻合，至此，差分约束问题被转化为了最短路问题

特殊情况的讨论

1. 存在负环

负环就是最短路可以无限小，所以就不存在最短路，那么上式就表示为$x[n-1]-x[0]\leq T$中的$T$可以无限小，即不存在这样的最大值

2. 终点不可达

如果出现了$dis[n-1]=inf$的情况，说明终点不可达到，此时对应的不等式意义就是$x[n-1]和x[0]$之间没有约束关系，任意取值都行，即取值有无限多种

3. 不等式组转化

对于不等号不相同的情况，可以考虑转化：

$$\begin{aligned} x[n-1]-x[0]\geq T&\Rightarrow x[0]-x[n-1]\leq -T\\ x[n-1]-x[0]<T&\Rightarrow x[n-1]-x[0]\leq T-1\\ x[n-1]-x[0]=T&\Rightarrow x[n-1]-x[0]\leq T\&\&x[n-1]-x[0]\geq T \end{aligned}$$

4. 其他问法&应用

如果是问$x[n-1]-x[0]$的最小值呢？那么只需要把不等号全部改为$\geq$，然后泡一下从$0到n-1$的最长路就行啦

另外会有一些类似于求$max(\frac{x[n-1]}{x[0]})$，此时需要做一些数学变换（比如取对数）就可以将其转换为差分约束系统开始搞了

习题

通常这种题的问法都比较绕口。。（导致读题跟阅读理解一样）

POJ 3159 Candies

题意：

给出若干组 同学B永远不会比同学A多拥有的糖果数量（即最大值），n号同学和1号同学拥有糖果数的最大差异（保证差异有限）

题解：

把题目翻译成数学语言就是给了一堆$x_B-x_A\leq W$的式子，求$max(x_n-x_1)$，差分约束走起，由于题目给了一定存在，因此不需要再判是否存在

注：此题会卡时间，请用堆优化Dijkstra

AC代码：

#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=1e8;
int n,m;
int cnt,head[30005],dis[30005];
struct Edge{
	int u,v,w,next;
}e[150005];

struct node{
	int u,dis;
	bool operator<(const node &rhs)const{
		return dis>rhs.dis;
	}
};
inline void addedge(int u,int v,int w){
	e[++cnt]=Edge{u,v,w,head[u]};
	head[u]=cnt;
}

inline void spfa(){
	for(int i=1;i<=n;i++) dis[i]=inf;
	priority_queue<node> q;
	q.push(node{1,0});
	dis[1]=0;
	while(!q.empty()){
		node q1=q.top();q.pop();
		int u=q1.u;
		if(q1.dis>dis[u]) continue;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(node{v,dis[v]});
			}
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
	}
	spfa();
	printf("%d\n",dis[n]);
	return 0;
}

POJ 3169 Layout

题意：

给出若干组两头牛之间的最大距离和最小距离，求1号牛和n号牛的最大可能距离（如果不存在输出-1，如果可以随便取值输出-2）

题解：

翻译过来就是给出若干组小于等于和大于等于的约数，求$max(x_n-x_1)$，差分约束

注：需要考虑负环和终点不可达的情况

AC代码：

#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int inf=1e8;
int n,m,k;
ll cnt,head[30005],dis[30005],ring[30005],vis[30005];
struct Edge{
	ll u,v,w,next;
}e[150005];
inline void addedge(ll u,ll v,ll w){
	e[++cnt]=Edge{u,v,w,head[u]};
	head[u]=cnt;
}

inline bool spfa(){
	for(int i=1;i<=n;i++) dis[i]=inf;
	queue<int> q;
	q.push(1);
	ring[1]=1;
	dis[1]=0;
	vis[1]=1;
	while(!q.empty()){
		ll u=q.front();q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next){
			ll v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				ring[v]=ring[u]+1;
				if(ring[v]>n) return true;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return false;
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	ll x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		addedge(x,y,z);
	}
	for(int i=1;i<=k;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		addedge(y,x,-z);
	}
	if(spfa()) printf("-1\n");
	else{
		printf("%lld\n",dis[n]>=inf?-2:dis[n]);
	}
	return 0;
}

POJ 1716 Integer Intervals

题意：

给出若干区间，求一个点集满足所有区间都至少有两个点在这个点集里，求这样的点集的最小大小

题解：

关键在于转化为差分约束问题，可以考虑$dis[x]表示[0,x]这个区间在点集内的点的个数$，那么题目就可以转化为（加一是为了防止数组下标有-1出现）

$$dis[r_i+1]-dis[l_i]\geq 2\\$$

除此之外，还有非常关键的题目隐含条件（都是整数点）

$$0\leq dis[i+1]-dis[i]\leq1$$

现在就可以建图+跑最短路了

AC代码：

#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
ll maxn=10005;
const int inf=1e8;
int n,m,k;
ll Max,cnt,head[30005],dis[30005],ring[30005],vis[30005];
struct Edge{
	ll u,v,w,next;
}e[150005];
inline void addedge(ll u,ll v,ll w){
	e[++cnt]=Edge{u,v,w,head[u]};
	head[u]=cnt;
}

inline bool spfa(){
	for(int i=0;i<=Max;i++) dis[i]=-inf;
	queue<int> q;
	q.push(0);
	dis[0]=0;
	vis[0]=1;
	while(!q.empty()){
		ll u=q.front();q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next){
			ll v=e[i].v,w=e[i].w;
			if(dis[v]<dis[u]+w){
				dis[v]=dis[u]+w;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}

int main(){
	scanf("%d",&n);
	ll x,y;
	Max=0;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&x,&y);
		addedge(x,y+1,2);
		Max=max(Max,y+1);//存区间最大值
	}
	for(int i=0;i<=Max;i++){
		addedge(i,i+1,0);
		addedge(i+1,i,-1);
	}
	spfa();
	printf("%lld\n",dis[Max]);
	return 0;
}

HDU 3666 THE MATRIX PROBLEM

这真是一道TMD无敌宇宙霹雳巨恶心的题，甚至还带点玄学算法，搞得我半夜十二点不能睡觉

题意：

给出一个$n*m$的矩阵，要求构造两个数列$an,b_m$使矩阵第$i$行元素乘上$a_i$，第$j$列元素除以$b_j$得到一个新矩阵$C$，且需要满足$C{i,j}\in [L,U]$，问能否构造成功？

题解：

这TM？？第一眼看到：神仙题？

考虑将题目条件转换为数学文字：

$$L\leq \frac{x_{i,j}\cdot A_i}{B_j}\leq U\Rightarrow \frac{L}{x_{i,j}}\leq \frac{A_i}{B_j}\leq\frac{U}{x_{i,j}}\\ 两边取对数，得出\\ log(\frac{L}{x_{i,j}})\leq log(A_i)-log(B_i)\leq log(\frac{U}{x_{i,j}})$$

可以差分约束+判负环搞起来了

什么？？TLE了！什么？传统判负环方法不行了？？

于是上网找到这道题TMD居然会卡时间卡得这么紧？？！

MARK 新姿势

于是查到有两种方案（玄学剪枝法）：

1. 一个节点更新次数大于$\sqrt{n}$就判定位负环（无法证明？有什么办法，这题只能这么胡搞）

2. 所有节点更新总次数大于$k*n$就判定为负环（一般k取2，然并卵，也是个玄学方法）

除此之外，我还发现我一直使用的判负环方法会WA？？

因此我得出结论：

对于此类题，先用我自己的判负环方法，如果WA了，改为更强的方法，如果还TLE，那么就用上面的玄学剪枝法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double inf=0x3f3f3f3f;
int n,m,k;
double l,r;
ll cnt,head[600005],ring[600005],vis[600005];
double dis[600005];
struct Edge{
	ll u,v,next;
	double w;
}e[3500005];
inline void addedge(ll u,ll v,double w){
	e[++cnt]=Edge{u,v,head[u],w};
	head[u]=cnt;
}

inline bool spfa(int st){
	memset(vis,0,sizeof(vis));
	memset(ring,0,sizeof(ring));
	for(int i=1;i<=n+m+10;i++) dis[i]=inf;
	queue<int> q;
	q.push(st);
	dis[st]=0;
	vis[st]=1;
	while(!q.empty()){
		ll u=q.front();q.pop();
		vis[u]=0;
		ring[u]++; //新判法
		if(ring[u]>sqrt(n+m)) return true; //超级玄学搞法
		for(int i=head[u];i!=-1;i=e[i].next){
			ll v=e[i].v;
			double w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return false;
}

int main(){
	while(~scanf("%d%d%lf%lf",&n,&m,&l,&r)){
		cnt=0;
		l=log2(l);
		r=log2(r);
		memset(head,-1,sizeof(head));
		double x;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%lf",&x);
				double temp=log2(x);
				addedge(n+j,i,r-temp);
				addedge(i,n+j,temp-l);
			}
		}
//		for(int i=1;i<=n+m;i++) addedge(0,i,0);
		if(spfa(1)) printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}