首页 > 代码库 > 差分约束系统小结
差分约束系统小结
百科是这样说的：如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
学习差分约束系统之前，必须掌握单源最短路径的算法（Bellman-ford、SPFA）。习惯上用SPFA解差分约束的题目。
解题思想有两种：
假设j > i，
1、由xj - xi >=w得到xj >= xi + w,建立一条从xi->xj的边权为w的边。然后用最长路算法。
2、由xj - xi >=w得到xi <= xj - w,建立一条从xj->xi的边权为-w的边。然后用最短路算法。
在具体建图的时候，为了避免重复，j+1或者i-1。
实际上，最长路和最短路算法的区别很小（SPFA模版）。
最长路算法中dist[]初始化为负无穷，松弛的时候是if(dist[v] < dist[u] + Map[u][v]) 。
最短路算法中dist[]初始化为正无穷，松弛的时候是if(dist[v] > dist[u] + Map[u][v]) 。
以具体的题目作为例子吧。
hdu1384
题目大意是：
给出一些区间[ai,bi]和每个区间最少需要ci个点，然后问总共最少需要几个点满足所有区间的要求。
由于1<=ai<=bi,所以ai-1或者bi+1都是没关系的，都是可以的。（下标从0开始和1开始都行，却不能是负数）
设s[i]是1~i 中需要的点的个数。则
s[j+1]-s[i]>=w。这只是题目给出的数据所能建的图。
但是有很多点是没有连通的。
有隐含条件 0=<s[i+1] - s[i] <=1 。
这样就可以做题了。
如果选择建立xj >= xi + w的关系来建图，就需要用最长路经来解题。dist[]初始化为负无穷。
具体的看代码：
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;const int N = 50010, M=150010;const int INF = 0x3f3f3f3f;struct node{ int to, w, next;};node edge[M];int head[N], dist[N], outq[N];bool vis[N];int tot;bool SPFA(int s, int n ){ int i,k; for(i=0;i<=n;i++) dist[i]=-INF; memset(vis,0,sizeof(vis)); memset(outq,0,sizeof(outq)); queue<int > q; while(!q.empty()) q.pop(); vis[s]=1; dist[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; outq[u]++; if(outq[u]>n) return 0 ; k=head[u]; while(k>=0) { if(dist[edge[k].to]-edge[k].w<dist[u]) { dist[edge[k].to]=dist[u]+edge[k].w; if(!vis[edge[k].to]) { vis[edge[k].to]=1; q.push(edge[k].to); } } k=edge[k].next; } } return 1;}void addedge(int i, int j ,int w){ edge[tot].to=j; edge[tot].w=w; edge[tot].next=head[i]; head[i]=tot++;}void init(){ memset(head,-1,sizeof(head)); tot=0;}int main(){ //freopen("test.txt","r",stdin); int n,m,i,j,k,w,a,b; while(scanf("%d",&m)!=EOF) { init(); a=INF,b=-INF; for(k=0;k<m;k++) { scanf("%d %d %d",&i,&j,&w); if(a>i) a=i; if(b<j+1) b=j+1; addedge(i,j+1,w); } for(i=a;i<=b;i++) { addedge(i,i+1,0); addedge(i+1,i,-1); } if(SPFA(a,b)) printf("%d\n",dist[b]); } return 0;}
差分约束系统小结