差分约束系统

简介

差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。

如何一个系统由n个变量和m个约束条件组成， 其中每个约束条件形如
x[i] - x[j] <= d (i, j ∈ [1, n], t ∈ [1, m])， 则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

如果 x[i] - x[j] <= d ， 那么从 j 到 i 链接一条长度为d的边。那么就是求最短路。
如果 x[i] - x[j] >= d ， 那么从 j 到 i 链接一条长度为d的边。那么就是求最长路。

判断有无解

判断图有没有负环即可，如果发现了负环，说明找到了矛盾。

用spfa判负环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool spfa(int s) {
    dis[s] = 0;
    vis[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = 0;
        tim[u]++;
        if (tim[u] > sqrt(n + m)) return 0;
        for (int i = head[u]; ~i; i = ed[i].ne) {
            int v = ed[i].v;
            if (dis[v] > dis[u] + ed[i].w) {
                dis[v] = dis[u] + ed[i].w;
                if (!vis[v])
                    q.push(v), vis[v] = 1;
            }
        }
    }
    return 1;
}
dfs判负环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
inline bool spfa(int u){
    vis[u] = 1;
    for (int i = head[u]; ~i; i = ed[i].ne){
        int v = ed[i].v, w = ed[i].w;
        if (dis[v] > dis[u] + w){
            if (vis[v]) {
                vis[v] = 0;
                return 0;
            }
            dis[v] = dis[u] + w;
            if (!spfa(v)) {
                vis[v] = 0;
                return 0;
            }
        }
    }
    vis[u] = 0;
    return 1;
}
int main(){
    for (int i = 1; i <= n; ++i){
        if (!spfa(i)){
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

例题 1. [SCOI2011]糖果

题目链接
这是一道没给数据范围的题， 而且还是一个很玄学的题， 最短路过不了（要是有大佬过了欢迎留言）最长路过了， 正向建超级源点过不了， 反向建过了。。
AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
 
#define eps 1e-8
#define ms(i, val) memset(i, val, sizeof i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 3e5 + 5;
const int M = 3e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 4557430888798830399;
 
inline int read() {
    int res = 0; bool f = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res + 1) : res;
}
struct edge {
    int u, v;ll w;
    int ne;
} ed[M];
int cnt, n, m, head[N], tim[N];
ll dis[N];
bool vis[N];
 
void init() {
    ms(vis, false);
    ms(head, -1);
    cnt = 0;
    ms(tim, 0);
}
inline void add(int u, int v, ll w) {
    ed[cnt] = {u, v, w, head[u]};
    head[u] = cnt++;
}
 
deque<int>q;
inline bool spfa(int u){
    dis[u] = 0;
    vis[u] = 1;
    q.push_back(u);
    while(!q.empty()){
        u = q.front();q.pop_front();
        vis[u] = 1;
        tim[u]++;
        if (tim[u] > sqrt(n + m)) return 0;
        for (int i = head[u]; ~i; i = ed[i].ne){
            int &v = ed[i].v;
            ll &w = ed[i].w;
            if (dis[v] < dis[u] + w){
                dis[v] = dis[u] + w;
                if (!q.empty() && dis[v] <= dis[q.front()]) q.push_back(v);
                else q.push_front(v);
                vis[v] = 1;
            }
        }
    }
    return 1;
}
 
 
int main() {
    int a, b, op;
    n = read(), m = read();
    init();
    for (int i = 0; i < m; ++i){
        op = read(), a = read(), b = read();
 
        if (op == 1) add(a, b, 0), add(b, a, 0);
        if (op == 2) add(a, b, 1);
        if (op == 3) add(b, a, 0);
        if (op == 4) add(b, a, 1);
        if (op == 5) add(a, b, 0);
    }
    for (int i = n; i >= 1; --i){
        add(0, i, 1);
    }
    ll ans = 0;
    if (spfa(0)){
        for (int i = 1; i <= n; ++i){
            ans += dis[i];
        }
        cout << ans << "\n";
    }
    else cout << "-1\n";
 
    return 0;
}

例题2. HDU3666. THE MATRIX PROBLEM

题目链接
隐藏比较深的差分约束了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

#define eps 1e-8
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1001;
const int INF = 0x3f3f3f3f;
const ll ll_max = 4557430888798830399;

struct edge {
    int u, v, ne;
    double w;
} ed[340444];

int cnt, n, m, head[N], tim[N];
bool vis[N];
double dis[N];
queue<int> q;

void init() {
    memset(tim, 0, sizeof tim);
    for (int i = 0; i <= m + n; ++i)
        dis[i] = INF, tim[i] = 0, head[i] = -1, vis[i] = 0;
    cnt = 0;
}

void add(int u, int v, double w) {
    ed[cnt].u = u, ed[cnt].v = v, ed[cnt].w = w;
    ed[cnt].ne = head[u];
    head[u] = cnt++;
}

int u, v;

bool spfa(int u) {
    vis[u] = 1;
    for (int i = head[u]; ~i; i = ed[i].ne){
        int &v = ed[i].v;
        double &w = ed[i].w;
        if (dis[v] > dis[u] + w){
            dis[v] = dis[u] + w;
            if (vis[v]){
                vis[v] = 0;
                return 0;
            }
            if (!spfa(v)){
                vis[v] = 0;
                return 0;
            }
        }
    }
    vis[u] = 0;
    return 1;
}
double L, U, x;
int main() {
    while (~scanf("%d%d%lf%lf", &n, &m, &L, &U)) {
        init();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                scanf("%lf", &x);
                add(j + n, i, log(U / x));
                add(i, j + n, log(x / L));
            }
        }
        int flag = 1;
        for (int i = 1; i <= n + m; ++i) {
            if (!spfa(i)) {
                puts("NO");
                flag = 0;
                break;
            }
        }
        if (flag)
            puts("YES");
    }
    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan