一個很好的差分約束總結：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 <cstdio> #include <cstring> #include <iostream> #include <queue> 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;queue<int>q;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\n",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 <iostream> #include <cstring> #include <cstdio> #include <queue> 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;queue<int>q;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\n");else printf("successful conspiracy\n");}return 0; }

　　bellman_ford版本，由于它是對各邊進行松弛，所以多加入了0點不用對其加超級源點了。知識要進行n次而不是n-1次了。。

#include <iostream> #include <cstring> #include <cstdio> #include <queue> 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\n");else printf("successful conspiracy\n");}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 <cstring> #include <cstdio> #include <iostream> #include <queue> #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;queue<int>q;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:\n",cas++);bool mark = spfa(0);if (mark){for (i = 1; i <= n; ++i)printf("%d %d\n",i,dis[i]);}else{printf("impossible\n");}printf("\n");}return 0; }

　　

?

總結

以上是生活随笔為你收集整理的差分约束 1:pku 1201 Intervals 2:pku 1364 King 3:hdu 1534的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。