差分约束

一般地，差分约束系统分两类：求最大差和最小差

求最小差
建立形如 A+B<=C 的不等式，在原图中添加边（A, C）边权为 B ，对建好的图跑最长路，如果存在负环，无解（判断条件为某点被更新了 n 次），n 为图中点的数量
求最大差
建立形如 A+B>=C 的不等式，在原图中添加边（A, C）边权为 B ，对建好的图跑最短路，如果存在负环，无解（判断条件为某点被更新了 n 次），n 为图中点的数量

原因如下：

对于线性规划问题，上述不等式的特点就是式子的左右两边都只有 1 个变量（ B 为常数）。这与图上的最短路是类似的。记从起点 s 出发，到各个定点的 v 的最短距离为 d（v），因此对于每条权值为 w 的边 e =（v，u），都有 d（v）+ w >= d（u）成立。反之，在满足全部这些约束的不等式的 d 中，d（v）- d（s）的最大值就是从 s 到 v 的最短距离。需要注意的是这里不是最小值，而是最大值对应着最小距离。

HDU1304

题意：
给你 n 个区间 [Ai, Bi]，每一个集合有一个指标Ci。求一个集合，使得这个集合至少涵盖每个区间内的 Ci 个数字。
问：满足上面条件的集合的最短长度是多少？

解法：

设 f(b) 为区间 [0,b] 之间包含的集合元素的个数，则对于不等式 f(b)-f(a-1) >= c ，建立一条 b 到 a-1 的边权值为 c。

除此之外还有隐含条件：0<=f(a)-f(a-1)<=1 则有边权关系 (a,a-1,0) 以及 (a-1,a,-1)；基于这三个不等式建图，则求的最长路即为最小值(集合) 。

因为这些点是从 0 开始的，所以我们将所有点的初始值都增加 1。

除此之外，我们还要建立一个源点与上述系统相连，由于隐含条件的存在这里就不需要了。

注意是多组数据。。mmp

 1 struct Edge {
 2     int from, to, w, next;
 3 } e[500001];
 4 int head[MAXN], vis[MAXN];
 5 int dist[MAXN];
 6 int N, m, tot;
 7 int l = INF, r = -1;
 8 
 9 void add_edge(int i, int j, int w) {
10     e[tot].from = i, e[tot].to = j, e[tot].w = w;
11     e[tot].next = head[i];
12     head[i] = tot++;
13 }
14 
15 void SPFA(int s) {
16     queue<int> q;
17     memset(dist, -63, sizeof(dist));
18     memset(vis, false, sizeof(vis));
19     q.push(s);
20     dist[s] = 0;
21     while (!q.empty()) {
22         int u = q.front();
23         q.pop();
24         vis[u] = false;
25         for (int i = head[u]; i != -1; i = e[i].next) {
26             int v = e[i].to;
27             if (dist[v] < dist[u] + e[i].w) {
28                 dist[v] = dist[u] + e[i].w;
29                 if (!vis[v]) {
30                     vis[v] = true;
31                     q.push(v);
32                 }
33             }
34         }
35     }
36     return;
37 }
38 
39 int main() {
40 #ifndef ONLINE_JUDGE
41     freopen("input.txt", "r", stdin);
42 #endif
43     int n;
44     while (scanf("%d", &n) != EOF) {
45         int u, v, w;
46         tot = 0;
47         memset(head, -1, sizeof(head));
48         for (int i = 1; i <= n; i++) {
49             scanf("%d%d%d", &u, &v, &w);
50             u++, v++;
51             add_edge(u - 1, v, w);
52             l = min(l, u);
53             r = max(r, v);
54         }
55         for (int i = l; i <= r; i++) {
56             add_edge(i - 1, i, 0);
57             add_edge(i, i - 1, -1);
58         }
59         SPFA(l - 1);
60         printf("%d
", abs(dist[r]));
61     }
62     return 0;
63 }

POJ3169

题意：有 N 只牛排成一条直线，有 ML 个牛关系好的信息（AL BL DL），代表牛 AL 和牛 BL 之间的距离不能大于 DL；类似的，给出 DL 个牛关系不好的信息（AD BD DD），代表牛 AD 和牛 BD 之间的距离不能大于 DD。求问牛 1 和牛 N 之间可能的最大距离，如果不存在输出 -1，结果为无限输出 -2，否则输出最大距离。

解法：由于没有给出明确关系只给出了大小关系，考虑差分方程求解

首先因为牛的站位和编号有关，那么我们可以得到不等式 1 ：$dist[i+1] ge dist[i]$，连一条从点 i+1 到点 i 的长度为 0 的边；

其次，根据亲密的牛的关系，我们有不等式 2 ：$dist[AL] + DL ge dist[BL]$，连一条从 AL 到 BL 的长度为 DL 的边；

再次，根据不亲密的牛的关系，有不等式3：$dist[BD] - DD ge dist[AD]$，连一条从 BD 到 AD 的长度为 -DD 的边。

由于题目要求最大距离，也就是求最短路，注意考虑负环的情况。

 1 int N, ML, DL;
 2 struct Edge {
 3     int from, to, w, next;
 4 } e[50010];
 5 int head[MAXN], vis[MAXN];
 6 int dist[MAXN];
 7 int sum[MAXN];
 8 int n, m, tot;
 9 
10 void add_edge(int i, int j, int w) {
11     e[tot].from = i, e[tot].to = j, e[tot].w = w;
12     e[tot].next = head[i];
13     head[i] = tot++;
14 }
15 
16 int SPFA(int s) {
17     queue<int> q;
18     for (int i = 1; i <= N; i++) dist[i] = INF, sum[i] = 0;
19     memset(vis, false, sizeof(vis));
20     q.push(s);
21     dist[s] = 0;
22     while (!q.empty()) {
23         int u = q.front();
24         q.pop();
25         vis[u] = false;
26         for (int i = head[u]; i != -1; i = e[i].next) {
27             int v = e[i].to;
28             if (dist[v] > dist[u] + e[i].w) {
29                 dist[v] = dist[u] + e[i].w;
30                 if (!vis[v]) {
31                     vis[v] = true;
32                     sum[v]++;
33                     if (sum[v] > N) return false;
34                     q.push(v);
35                 }
36             }
37         }
38     }
39     return true;
40 }
41 
42 int main() {
43     // freopen("input.txt", "r", stdin);
44     scanf("%d%d%d", &N, &ML, &DL);
45     int u, v, w;
46     tot = 0;
47     SET(head);
48     for (int i = 2; i <= N; i++) {
49         add_edge(i, i - 1, 0);
50     }
51     for (int i = 1; i <= ML; i++) {
52         scanf("%d%d%d", &u, &v, &w);
53         add_edge(u, v, w);
54     }
55     for (int i = 1; i <= DL; i++) {
56         scanf("%d%d%d", &u, &v, &w);
57         add_edge(v, u, -w);
58     }
59     if (!SPFA(1))
60         printf("-1
");
61     else if (dist[N] == INF)
62         printf("-2
");
63     else
64         printf("%d
", dist[N]);
65     return 0;
66 }