一个很好的差分约束总结：http://972169909-qq-com.iteye.com/blog/1185527
第一：
感觉难点在于建图
第二：
①：对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值
②：对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值
③：存在负环的话是无解
④：求不出最短路（dist[ ]没有得到更新）的话是任意解
第三：
一种建图方法：
设x[i]是第i位置（或时刻）的值（跟所求值的属性一样），那么把x[i]看成数列，前n项和为s[n]，则x[i] = s[i] - s[i-1]；
那么这样就可以最起码建立起类似这样的一个关系：0 <= s[i] - s[i-1] <= 1;
其他关系就要去题目探索了
以上总结为转载：
http://poj.org/problem?id=1201
题意是：给定n个闭区间，[ai,bi]，求一个集合满足他与每个集合相交的点数最少为ci，且拥有最少的元素个数，输出最少元素个数；
首先根据1 <= ci <= bi - ai+1 的 s[bi + 1] - s[ai] >= ci; 然后根据0<=x[i]<= 1 得到 s[i] -s[i - 1] >= 0 s[i - 1] - s[i] >= -1; 由于会出现0点没然后-1就无意思，于是我们转化成
s[i ＋1] - s[i] >= 0 [i] - s[i +1] >= -1 求最长路径得到最小值；
spfa实现：
#include
#include
#include
#include
using namespace std;const int maxn = 50005;
const int inf = 999999999;
struct node
{int v,w;int next;
}e[maxn*5];int dis[maxn],ind[maxn],pre[5*maxn];
int cnt,n,mi,ma;
bool inq[maxn];void init()
{cnt = 0; mi = inf; ma = -inf;for (int i = 0; i < maxn; ++i){inq[i] = false;ind[i] = 0;pre[i] = -1;}
}
void addedge(int u,int v,int w)
{e[cnt].v = v; e[cnt].w = w;e[cnt].next = pre[u];pre[u] = cnt++;
}
bool spfa(int u)
{int i;for (i = mi; i <= ma; ++i) dis[i] = -inf;dis[u] = 0;queueq;q.push(u); inq[u] = true;while (!q.empty()){int cur = q.front(); q.pop();if (++ind[cur] > n) return false;inq[cur] = false;for (i = pre[cur]; i != -1; i = e[i].next){int v = e[i].v; int w = e[i].w;if (dis[v] < dis[cur] + w){dis[v] = dis[cur] + w;if (!inq[v]){q.push(v);inq[v] = true;}}}}return true;
}
int main()
{int i,a,b,c;init();scanf("%d",&n);for (i = 0; i < n; ++i){scanf("%d%d%d",&a,&b,&c);addedge(a,b + 1,c);mi = min(mi,a);ma = max(ma,b + 1);}for (i = mi; i <= ma; ++i){addedge(i,i + 1,0);addedge(i + 1,i,-1);}spfa(mi);printf("%d
",dis[ma] - dis[mi]);return 0;
}
http://poj.org/problem?id=1364
题意是有序列： S = {a1, a2, ..., an}定义：Si = {aSi, aSi+1, ..., aSi+ni} Si > ki 或者 Si < ki
假设s[i] = a[1] + a[2] + ...... + a[i]; 则有si = s[si + ni] - s[si -1] ====> s[si + ni] - s[si - 1] >ki s[si + ni] - s[si - 1] < ki;由于差分约束的约束条件是<= >=
转化的 ： s[si - 1] - s[si + ni] <= -ki - 1 s[si + ni] - s[si - 1] <= ki - 1 a-b <= c形式求最短路，判断是否存在解即可：
注意：
1：由> ，< 到 <= ,>= 的转化；
2：由于图不一顶连通，即spfa()的启点不确定，所以要建立超级源点：
#include
#include
#include
#include
using namespace std;const int maxn = 207;
const int inf = 999999999;struct node
{int w,v;int next;
}e[maxn*maxn];
int pre[maxn*maxn],ind[maxn],dis[maxn];
int cnt,n,m;
bool inq[maxn];void init()
{cnt = 0;memset(e,0,sizeof(e));memset(ind,0,sizeof(ind));memset(pre,-1,sizeof(pre));memset(inq,false,sizeof(inq));
}
void add(int u,int v,int w)
{e[cnt].v = v; e[cnt].w = w;e[cnt].next = pre[u];pre[u] = cnt++;
}
bool spfa(int u)
{int i;queueq;for (i = 0; i < maxn; ++i) dis[i] = inf;dis[u] = 0;q.push(u); inq[u] = true;while (!q.empty()){int cur = q.front(); q.pop();if (++ind[cur] > n + 1) return false;//加入了超级源点故要大于n+1inq[cur] = false;for (i = pre[cur]; i != -1; i = e[i].next){int v = e[i].v, w = e[i].w;if (dis[v] > dis[cur] + w){dis[v] = dis[cur] + w;if (!inq[v]){inq[v] = true;q.push(v);}}}}return true;
}
int main()
{int i,si,ni,ki;char op[5];while (~scanf("%d",&n)){if (!n) break; scanf("%d",&m);init();for (i = 0; i < m; ++i){scanf("%d%d%s%d",&si,&ni,op,&ki);if (op[0] == 'l')add(si - 1,si + ni,ki - 1);elseadd(si + ni,si - 1,-ki - 1);}for (i = 0; i <= n; ++i) add(n + 1,i,0);//建立超级源点bool mark = spfa(n + 1);if (mark) printf("lamentable kingdom
");else printf("successful conspiracy
");}return 0;
}
bellman_ford版本，由于它是对各边进行松弛，所以多加入了0点不用对其加超级源点了。知识要进行n次而不是n-1次了。。
#include
#include
#include
#include
using namespace std;const int maxn = 207;
const int inf = 999999999;struct node
{int u,v,w;
}e[maxn];int dis[maxn];
int n,m,cnt;
void add(int u,int v,int w)
{e[cnt].u = u;e[cnt].v = v;e[cnt].w = w;cnt++;
}
bool bellman_ford()
{int i,j;for (i = 0; i <= n; ++i) dis[i] = inf;dis[0] = 0;bool flag;for (i = 0; i <= n; ++i){flag = true;for (j = 0; j < m; ++j){int u = e[j].u;int v = e[j].v;int w = e[j].w;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;flag = false;}}if (flag) break;}return flag;
}
int main()
{int i,si,ni,ki;char op[4];while (~scanf("%d",&n)){if (!n) break; scanf("%d",&m);cnt = 0;for (i = 0; i < m; ++i){scanf("%d%d%s%d",&si,&ni,op,&ki);if (op[0] == 'g')add(si + ni,si - 1,-ki - 1);elseadd(si - 1,si + ni,ki - 1);}bool mark = bellman_ford();if (mark) printf("lamentable kingdom
");else printf("successful conspiracy
");}return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1534
题意：就是给你n个工程，每个工程必须在连续的V[i]时间内完成，这些工程在完成顺序上有四种形式的限制。
输入形式为 *** a,b s[i]表示工程i的开始时间，v[i]表示必须花费连续v[i]的时间才能完成。由于是求最小值，所以化简成 a - b >= c求最长路得最小值的形式；
FAS: b开始后a完成。 s[a] ＋v[a] >= s[b] -----> s[a] - s[b] >= -v[a]
FAF: b完成后a完成。 s[a] + v[a] >= s[b] + v[b]------> s[a] - s[b] >= v[b] - v[a];
SAF: b完成后a开始。 s[a] >= s[b] + v[b]-------> s[a] - s[b] >= v[b];
SAS: b开始后a开始。s[a] >= s[b]-------> s[a] - s[b] >= 0;
建图，然后求解，得到的dis[i]就是每个项目在最短的时间消耗下的开始时间：
#include
#include
#include
#include
#define maxn 50004
using namespace std;struct node
{int v,w;int next;
}g[maxn];
int pre[maxn],ind[maxn],cnt;
bool inq[maxn];
int n,V[maxn],dis[maxn];
const int inf = 99999999;void init()
{cnt = 0;memset(g,0,sizeof(g));memset(pre,-1,sizeof(pre));
}
void add(int u,int v,int w)
{g[cnt].v = v;g[cnt].w = w;g[cnt].next = pre[u];pre[u] = cnt++;
}
bool spfa(int u)
{int i;queueq;for (i = 0; i <= n; ++i){dis[i] = -inf;inq[i] = false;ind[i] = 0;}dis[u] = 0;q.push(u); inq[u] = true;while (!q.empty()){int cur = q.front(); q.pop();if (++ind[cur] > n + 1) return false;for (i = pre[cur]; i != -1; i = g[i].next){int v = g[i].v, w = g[i].w;if (dis[v] < dis[cur] + w){dis[v] = dis[cur] + w;if (!inq[v]){q.push(v);inq[v] = true;}}}inq[cur] = false;}return true;
}
int main()
{int i,cas = 1,a,b;while (~scanf("%d",&n)){if (!n) break;init();for (i = 1; i <= n; ++i) scanf("%d",&V[i]);char op[5];while (scanf("%s",op)){if (op[0] == '#') break;scanf("%d%d",&a,&b);if (!strcmp(op,"FAS")) add(b,a,-V[a]);else if (!strcmp(op,"FAF")) add(b,a,V[b] - V[a]);else if (!strcmp(op,"SAF")) add(b,a,V[b]);else add(b,a,0);}for (i = 1; i <= n; ++i) add(0,i,0);printf("Case %d:
",cas++);bool mark = spfa(0);if (mark){for (i = 1; i <= n; ++i)printf("%d %d
",i,dis[i]);}else{printf("impossible
");}printf("
");}return 0;
}