放一篇写的很好的博客：http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
个人感觉我差分约束还是不是很熟。
先总结一下遇见的差分约束题目类型：
1. 给定m条约束关系，求可行解
这种题目是需要建一个超级源点，向每个点连一条权值为0的边，之后v,u建有向边，跑最短最长都可以。
最后0到各个点的dis就是可行解
2. 给定m条约束关系，求[n] - [1]最大最小值。
这种类型就不需要超源，直接v,u建有向边，最大值跑最短路，最小值跑最长路
3. 给定m条约束关系，求[n] - [1]解的情况。
求最大值的最短路无解是有负环，最小值的最长路是正环。dis[n]为INF or -1 时无数解。
4. 给定m条约束关系，求未知量最值的情况。
未知条件约束是指在不等式的右边不一定是个常数，可能是个未知数，可以通过枚举这个未知数，然后对不等式转化成差分约束进行求解。（一般可以二分）
放几个自己需要注意的点：
1.保证有解就可以考虑dij
2.求最大值的最短路无解是有负环，最小值的最长路是正环。dis[n]为INF or -1 时无数解。
3. 小于号与小于等于号的转换。
4. 约束条件为a - b <= c时，建有向边b-a；为 >=时，建有向边a-b
模板题。就是题型1的解法。
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; // 2122219134 const int maxn = 5005 + 10; const int maxm = 1e4 + 10; struct node { int to; int w; int nex; }edge[maxm]; int tot,n,m; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { memset(dis, INF, sizeof(dis));//初始化dis queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to, w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] >= n) return 1; } } } } return 0; } int main() { init(); int u, v, w, op; cin >> n >> m; while (m--) { cin >> u >> v >> w; add(v, u, w); } for (int i = 1; i <= n; ++i) add(0, i, 0); if (bfs_spfa(0)) cout << "NO" << endl; else for (int i = 1; i <= n; ++i) cout << dis[i] << " "; return 0; }
题意：分糖，n个小朋友，m个关系，AB间关系的意思是A的糖果最多比B少w个，w为关系的权。
求1号和n号最多能差多少糖果。
（题型2）这道题的关系是B-A<=W，所以就是AB建有向边跑最短路即可。
解法：这道题卡一般的SPFA，但是由于题目保证有解，所以我们就可以直接用堆优化dij来跑。
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; // 2122219134 const int maxn = 3e4 + 10; const int maxm = 2e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int tot,n,m; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } void dijkstra(int s) { memset(dis, INF, sizeof(dis));//初始化dis priority_queue<pii,vector<pii>,greater<pii> > q;//从小到大 dis[s] = 0; q.push({dis[s],s}); while(!q.empty()) { int now = q.top().second; q.pop(); if(vis[now]) continue; vis[now] = 1; for(int i = head[now]; i != -1; i = edge[i].nex) { int v = edge[i].to; if(dis[v] > dis[now] + edge[i].w) { dis[v] = dis[now] + edge[i].w; q.push({dis[v],v}); } } } } int main() { init(); int u, v, w, op; scanf("%d%d", &n, &m); while (m--) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); } dijkstra(1); cout << dis[n] << endl; return 0; }
差分约束条件：
- b <= a + L 奶牛 A 和奶牛 B 至多相隔 L 的距离。
- a <= b - D 奶牛 A 和奶牛 B 至少相隔 D 的距离。
- si <= si+1 后一头奶牛的距离大于前一头
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; // 2122219134 const int maxn = 3e4 + 10; const int maxm = 2e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int tot,n,m1,m2; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { memset(dis, INF, sizeof(dis));//初始化dis queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to, w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] >= n) return 1; } } } } return 0; } int main() { init(); int u, v, w; scanf("%d%d%d", &n, &m1,&m2); while (m1--) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); } while (m2--) { scanf("%d%d%d", &u, &v, &w); add(v, u, -w); } for (int i = 1; i <= n; ++ i) add(i+1, i, 0); if (bfs_spfa(1)) cout << -1 << endl; else { if (dis[n] > INF / 2) cout << -2 << endl; else cout << dis[n] << endl; } return 0; }
非常经典的区间差分约束的题目。以下来自上述博客：
【例题2】给定n（n <= 50000）个整点闭区间和这个区间中至少有多少整点需要被选中，每个区间的范围为[ai, bi]，并且至少有ci个点需要被选中，其中0 <= ai <= bi <= 50000，问[0, 50000]至少需要有多少点被选中。
这类问题就没有线性约束那么明显，需要将问题进行一下转化，考虑到最后需要求的是一个完整区间内至少有多少点被选中，试着用d[i]表示[0, i]这个区间至少有多少点能被选中，根据定义，可以抽象出 d[-1] = 0，对于每个区间描述，可以表示成d[ bi ] - d[ ai - 1 ] >= ci，而我们的目标要求的是 d[ 50000 ] - d[ -1 ] >= T 这个不等式中的T，将所有区间描述转化成图后求-1到50000的最长路。
这里忽略了一些要素，因为d[i]描述了一个求和函数，所以对于d[i]和d[i-1]其实是有自身限制的，考虑到每个点有选和不选两种状态，所以d[i]和d[i-1]需要满足以下不等式： 0 <= d[i] - d[i-1] <= 1 （即第i个数选还是不选）
这样一来，还需要加入 50000*2 = 100000 条边，由于边数和点数都是万级别的，所以不能采用单纯的Bellman-Ford ，需要利用SPFA进行优化，由于-1不能映射到小标，所以可以将所有点都向x轴正方向偏移1个单位（即所有数+1）。
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; // 2122219134 const int maxn = 5e4 + 10; const int maxm = 5e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int tot,n,m1,m2; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { memset(dis, -INF, sizeof(dis));//初始化dis queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to, w = edge[i].w; if(dis[v] < dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] >= n) return 1; } } } } return 0; } int main() { init(); int u, v, w; scanf("%d", &n); for (int i = 0; i <= 50000; i++) { add(i, i+1, 0); add(i+1, i, -1); } for (int i = 1; i <= n; i++) { scanf("%d%d%d", &u, &v, &w); add(u-1, v, w); } bfs_spfa(0); printf("%d\n", dis[50000]); return 0; }
这道题主要就是考 > 转化为 >=。
题面好长。我是看题解的。
这里因为0是有用过的所以就选择n+1作为超源。
因为0到n+1总共有n+2个点，所以spfa里的入队次数要改成>=n+2
题目大意；
已知一个序列a[1], a[2], ……, a[n]，给出它的若干子序列以及对该子序列的
约束条件，例如a[si], a[si+1], a[si+2], ……, a[si+ni]，且a[si]＋a[si+1]
＋a[si+2]＋……＋a[si+ni] < or > ki。求是否存在满足以上m个要求的数列。是
则输出“lamentable kingdom”,否则输出“successful conspiracy”。
解题思路：
s[a] + s[a+1] + …… + s[b] < c 可以转化成前n项和sum[b] - sum[a - 1] < c，
为了能用Bellman_Ford,即将< 转化成 <= ，sum[b] - sum[a - 1] <= c - 1。
转化为最长路或者最短路来判断是否有解都可以。
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; // 2122219134 const int maxn = 5e4 + 10; const int maxm = 5e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int tot,n,m; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { memset(dis, INF, sizeof(dis));//初始化dis queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to, w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] > n+2) return 1; } } } } return 0; } int main() { while(~scanf("%d",&n)&&n) { scanf("%d",&m); init(); for(int i=0;i<m;++i) { int a,b,c; string op; cin>>a>>b>>op>>c; if (op[0]=='g') add(a+b,a-1,-c-1); else add(a-1,a+b,c-1); } for (int i=0;i<=n;++i) add(n+1,i,0); if (!bfs_spfa(n+1)) printf("lamentable kingdom\n"); else printf("successful conspiracy\n"); } return 0; }
题意：给定n个区间，你需要挑选出一个集合，使得集合中的元素与每个区间的交集>=2，输出集合元素的最小数量。
题解：因为求最小值，所以用最长路。最长路需要把约束条件换成 >=。建边见Note4.
约束条件： B - A >= 2
A - A-1 <= 1
A-1 - A >= 0
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; // 2122219134 const int maxn = 5e4 + 10; const int maxm = 5e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int maxx; int tot,n,m; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { memset(dis, -INF, sizeof(dis));//初始化dis queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to, w = edge[i].w; if(dis[v] < dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; // if (++cnt[v] >= maxx) return 1; } } } } return 0; } int main() { while (~scanf("%d",&n)) { init(); maxx = 0; for (int i = 1, u, v, w; i <= n; ++i) { scanf("%d%d", &u, &v); add(u, v+1, 2); maxx = max(v+1, maxx); } for (int i = 0; i < maxx; ++ i) { add(i+1, i, -1), add(i, i+1, 0); } bfs_spfa(0); cout << dis[maxx] << endl; } return 0; }
这里有几个需要注意的点。
首先约束条件是：B - A <= D (在按高度升序排列下，B的标号要大于A的标号）其实关于这点我不是特别明白，似乎是一个贪心
A+1 - A <= -1 （房子位置不重合）
UPD:
1.两个相邻点之间最小距离为一，则有d[i+1]-d[i]>=1,等价于 d[i]-d[i+1]<=-1;
2.高度最接近的两个点的最大距离为m,按距离排序之后可有 d[j+1]-d[j]<=m; 查分约束系统的条件找出来了；
剩下就是构图的事了。
由的d[i]-d[i+1]<=-1 的编辑条件可知，我们给各个点制定了一个方向，就是从左到右是依次增大的。
这就限定了的d[j+1]-d[j]<=m的连边条件，必须是由对应的序号小的点连向序号大的点，才对应了题目中的swap操作。
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x7fffffff; // 这里要改得大一些，虽然我的0x3f3f3f3f也过了 const int maxn = 5e4 + 10; const int maxm = 5e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int maxx; int tot,n,m; int head[maxn], dis[maxn], cnt[maxn]; int vis[maxn]; void init(){ memset(cnt, 0, sizeof(cnt));//cnt[i]记录i入队的次数 memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { // memset(dis, -INF, sizeof(dis));//初始化dis for (int i = 1; i <= 1000; ++ i) dis[i] = INF; queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to, w = edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] >= n) return 1; } } } } return 0; } struct House { int id, height; }house[maxn]; int main() { int T; scanf("%d", &T); for (int Ti = 1; Ti <= T; ++ Ti) { int d; scanf("%d%d", &n, &d); init(); for (int i = 1, w; i <= n; ++i) { scanf("%d", &w); house[i].id = i, house[i].height = w; if (i != n) add(i+1,i,-1); } sort(house+1, house+1+n, [](House a, House b){return a.height < b.height;}); for (int i = 1; i < n; ++ i) { int u = house[i].id; int v = house[i+1].id; if (u > v) swap(u, v); add(u, v, d); } int s = house[1].id; int t = house[n].id; if (s > t) swap(s, t); if (bfs_spfa(s)) dis[t] = -1; printf("Case %d: %d\n", Ti, dis[t]); } return 0; }
给你一个N*M的矩阵，给你两个数L和U（L <= U）问你是否存在这样的N+M个数字（计作A1….AN, B1…..BM），
使矩阵中任意元素Xij，满足：
L <= (Xij * Ai) / Bj <= U
题解：
差分约束，这道题构造差分约束方程特别巧妙。
转换成：Xij * Ai - U * Bj <= 0
L * Bj - Xij * Ai <= 0
由于差分约束中xi - xj <= val 方程的xi与xj前面不能有系数。
利用log运算将乘法转换成为加法，成为了标准的差分约束方程。
注意：
判断有无解（负环）的时候，如果用spfa，不能用入队次数大于N来判断，会超时。
有如下两种比较可靠的方法（一般情况下）
1：某个点入队次数大于sqrt(N)的时候
2：所有入队次数大于T * （N + M），其中T一般取2
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> #pragma GCC optimize(2) using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int maxm = 5e5 + 10; struct node { int to; double w; int nex; }edge[maxm]; int tot, n, m; int head[maxn]; double dis[maxn]; void init(){ memset(head, -1, sizeof(head)); tot = 0; } void add(int u, int v, double w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } bool bfs_spfa(int s) { int vis[maxn] = {0}; int cnt[maxn] = {0}; for (int i = 1; i <= n+m; ++ i) dis[i] = INF; queue<int> q; q.push(s); vis[s] = 1, dis[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; double w = edge[i].w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] >= (n+m+1)) return 1; } } } } return 0; } int main(void){ double L, U; while(~scanf("%d%d%lf%lf",&n,&m,&L,&U)){ init(); L = log2(L);U = log2(U); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ double tp;scanf("%lf",&tp); tp = log2(tp); int x = i,y = j+n; add(x,y,tp-L); add(y,x,U-tp); } } if (!bfs_spfa(1)) printf("YES\n"); else printf("NO\n"); } return 0; }
这题非常好！
题意：有一个超市需要一些出纳员，已给出这个超市在各个时间段（0-1，1-2，2-3...共24个时间段）至少需要的出纳员数目，
现在前来应聘有n个人，每个人都有一个固定的开始工作的时间，这也意味着从这个时间开始他要连续工作8个小时。在满足这
个超市对出纳员的需求的前提下，让你求出最少雇佣的出纳员人数。
need[i]表示在第 i 个小时至少也要的人数，work[i]表示应聘者中可以在第i个小时开始工作的人数,s[i]表示前i个小时雇佣的人数，
x[ i ]表示第 i 个小时雇佣的人数。 s[i] - s[i - 1] = x[i]
约束条件：
（1） 0<= x[i] <= x[ i ] ,转化为 0 <= s[ i ] - s[i - 1] <= work[ i ]
（2） i >= 8 时：need[ i ] <= x[i] + x[i - 1] + x[i - 2] + x[i - 3] + x[i - 4] + x[i - 5] + x[i - 6] + x[i - 7]
转化为 need[ i ] <= s[ i ] - s[i - 8]
i < 8 时：s[ i ] +s[ 24 ] -s[16 + i] >= need[i] (不清楚的可以模拟一下)
（3）对上面的S[24]我们不知道它的值，但我们知道它表示前24个小时所雇用的总人数，也就是我们要求的结果sum.因此对于未知
的sum，我们需要从0到n枚举sum。需要再建一条边即：s[24] - s[0] >= sum
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> #include<cmath> #include<string> #include<map> #include<queue> #pragma GCC optimize(2) using namespace std; #define pii pair<int,int> typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 10; const int maxm = 2e5 + 10; struct node { int to; int w; int nex; }edge[maxm]; int tot, n, m; int head[maxn]; int dis[maxn]; int work[maxn] = {0};//work[i]表示在第 i 个小时开始工作的人数 int need[maxn];//应聘者中可以在第i个小时开始工作的人数 void init(){ memset(head, -1, sizeof(head)); tot = 0; } void add(int u, int v, int w){ edge[tot] = {v, w, head[u]}; head[u] = tot++; } void getmap(int sum){ for(int i = 1; i <= 24; ++i){ add(i - 1, i, 0); add(i, i - 1, -work[i]); if(i >= 8) add(i - 8, i, need[i]); else add(16 + i, i, need[i] - sum); } add(0, 24, sum); } bool bfs_spfa(int sum) { int vis[maxn] = {0}; int cnt[maxn] = {0}; for (int i = 1; i <= 24; ++ i) dis[i] = -INF; queue<int> q; q.push(0); vis[0] = 1, dis[0] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; int w = edge[i].w; if (dis[v] < dis[u] + w) { dis[v] = dis[u] + w; if (!vis[v]) { q.push(v), vis[v] = 1; if (++cnt[v] >= 24) return 0; } } } } return dis[24] == sum;; } int main (){ int T; int OK, st; scanf("%d", &T); while(T--){ OK = 0; memset(need, 0, sizeof(need)); memset(work, 0, sizeof(need)); for(int i = 1; i <= 24; ++i) scanf("%d", &need[i]); scanf("%d", &n); for(int i = 0; i < n; ++i){ scanf("%d", &st); work[st + 1]++; } for(int i = 0; i <= n; ++i){ init(); getmap(i); if(bfs_spfa(i)){ OK = 1; printf("%d\n", i); break; } } if(!OK) printf("No Solution\n"); } return 0; }