差分约束 | Kite-chaser

差分约束

2019-10-27

图论真的是博大精深。

前言

如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。

正文

观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边(i,j)，边权为bk。我们再增加一个源点s,s与所有定点相连，边权均为0。对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终{d[ i]}即为一组可行解。
例：d[x]-d[y]>=Z
如果想连边后求最长路那么将不等式变形为这种形式 d[x]>=d[y]+z y---x连一条权值为z的边
求最短路则变形成d[y]<=d[x]-z x---y连一条权值为-z的边。
如果是别的不等式，也可以根据情况变形。
为什么一定要用SPFA呢，因为这个系统可能无解。当最长路出现正环的时候或最短路出现负环的时候，这个系统就无解惹。其实，最长最短都差不多，视情况而定。

EG

P1993 小K的农场

题目描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：

农场a比农场b至少多种植了c个单位的作物，
农场a比农场b至多多种植了c个单位的作物，
农场a与农场b种植的作物数一样多。

但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

Solve

建图，求最长路。

a-b>=c,从b向a建一条边权为c的边。
a-b<=c等于b-a<=-c,从a向b建一条边权为-c的边。
a=b，等于a-b>=0或b-a>=0，双向建边，权值为0。
每种情况分析完毕。
超级源点为0。向每一个点建一条权值为0的边。
SPFA跑最长路。
一种玄学优化方式，用DFS优化SPFA，直接跑SPFA会T飞的。
在判负环中可以用DFS或用栈代替队列来优化SPFA，但是在没有负环的情况请小心使用。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=23333333;
const int N=50005;
int n,m;
int num,x,y,z;
int first[N],nxt[N],to[N],dist[N],len;
int cnt[N],dis[N];
bool vis[N];
inline int read(){
    int k=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        k=(k<<1)+(k<<3)+(ch^48);
        ch=getchar();
    }
    return k*f;
}
void add(int u,int v,int w){
	to[++len]=v;
	dist[len]=w;
	nxt[len]=first[u];
	first[u]=len;
}
bool spfa(int u){
	vis[u]=1;
	for(int i=first[u];i!=-1;i=nxt[i]){
		if(dis[to[i]]<dis[u]+dist[i]){
			dis[to[i]]=dis[u]+dist[i];
			if(vis[to[i]]) return 0;
			if(!spfa(to[i])) return 0;
		}
	}
	vis[u]=0;
	return 1;
}
int main()
{
	memset(first,-1,sizeof(first));
	n=read();m=read();
	for(int i=1;i<=m;i++){
		num=read();x=read();y=read();
		if(num==1) z=read(),add(y,x,z);
		else if(num==2) z=read(),add(x,y,-z);
		else if(num==3) add(x,y,0),add(y,x,0);
	}
	for(int i=1;i<=n;i++) add(0,i,0),dis[i]=-maxn;;
	if(spfa(0)) printf("Yes");
	else printf("No");
	return 0;
}

后言

由此观之，许多看似后无头绪的题，其实可以用图论解决。就好像有指向性的状态可以用DAG建模。然后用相应的图论方法解决。所以OI题也要注意建模。

前言

正文

EG

P1993 小K的农场

题目描述

Solve

Code

后言

相关例题