• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

差分约束基本讲解

4天前 8次浏览

[begin{align}
x_1-x_0<=2 tag{1} \
x_2-x_0<=7 tag{2} \
x_3-x_0<=8 tag{3} \
x_2-x_1<=3 tag{4} \
x_3-x_2<=2 tag{5}
end{align}
]

[begin{align}
x_3-x_0<=8 tag{式3} \
x_3-x_0<=9 tag{式2+式5} \
x_3-x_0<=7 tag{式1+式4+式5}
end{align}
]

1. 0 -> 3，长度为 8

2. 0 -> 2 -> 3，长度为 7 + 2 = 9

3. 0 -> 1 -> 2 -> 3，长度为 2 + 3 + 2 = 7

差分约束与最短路

[begin{align}
x_1-x_0<2 notag{} \
x_2-x_0<7 notag{} \
x_3-x_0<8 tag{去掉等号后} \
x_2-x_1<3 notag{} \
x_3-x_2<2 notag{}
end{align}
]

(x_i) 被限定只能是整数时，这个转换就会非常简单，

[(x_i-x_j<c_k) ↔ (x_i-x_j<=c_k-1) notag{}
]

总结

1. 如果要求最大值，则想办法把每个不等式变为标准 (x_i-x_j<=c_k) 的形式，然后建立一条从 (j)(i) 权值为 (c_k) 的边，最后求最短路径即可。
2. 如果要求最小值，则想办法把每个不等式变为标准 (x_i-x_j>=c_k) 的形式，然后建立一条从 (j)(i) 权值为 (c_k) 的边，最后求最长路径即可。

基本题

CodeVS 4416 – FFF 团卧底的后宫

``````#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>

const int MAXN = 1000;
const int MAXM = 10000;

struct Edge;
struct Node;

struct Node {
Edge *edges;
bool inQueue;
int dist;
int count;
} nodes[MAXN];

struct Edge {
Node *from, *to;
int w;
Edge *next;

Edge(Node *from, Node *to, int w) : from(from), to(to), w(w), next(from->edges) {}
};

int n, m, k;

inline void addEdge(int from, int to, int w) {
nodes[from].edges = new Edge(&nodes[from], &nodes[to], w);
}

inline bool bellmanFord() {
std::queue<Node *> q;

q.push(&nodes[0]);
while (!q.empty()) {
Node *node = q.front();
q.pop();
node->inQueue = false;

for (Edge *edge = node->edges; edge; edge = edge->next) {
if (edge->to->dist > node->dist + edge->w) {
edge->to->dist = node->dist + edge->w;

if (!edge->to->inQueue) {
edge->to->inQueue = true;
edge->to->count++;
q.push(edge->to);

if (edge->to->count > n) {
return false;
}
}
}
}
}

return true;
}

int main() {
scanf("%d %d %d", &n, &m, &k);

for (int i = 0; i < n; i++) {
nodes[i].dist = INT_MAX;
}

nodes[0].dist = 0;

for (int i = 0; i < m; i++) {
int a, b, d;
scanf("%d %d %d", &a, &b, &d);
a--, b--;

// \$b - \$a <= d
// \$a + d >= \$b
}

for (int i = 0; i < k; i++) {
int a, b, d;
scanf("%d %d %d", &a, &b, &d);
a--, b--;

// b - a >= d
// a - b <= -d
// b + -d >= a
}

if (!bellmanFord()) {
puts("-1");
} else {
if (nodes[n - 1].dist == INT_MAX) {
puts("-2");
} else {
printf("%dn", nodes[n - 1].dist);
}
}

return 0;
}
``````

参考

• 差分约束系统，维基百科
• 差分约束，博客园
• 差分约束系统学习 , 个人博客