差分约束

时间复杂度：

  • 用最短路算法(spfa)实现

用途

  1. 求不等式组的可行解
  2. 如何求最大值和最小值

知识点如下；

差分约束
差分约束

  • 差分约束如何建图：
  • 首先明确，求最短路用 i <= j + x 来更新距离，含义为 j->i 边权为x，文字表示为i可用j来更新，求最长路用 i >= j + x 来更新距离，同理。
  • 求最小值( >= x的最小值)，所有的不等式化为i >= j + x，添边:add(j, i, x)，求x0到每个点xi的最长路。
  • 求最大值( <= x的最大值)，所有的不等式化为i <= j + x，添边为add(j, i, x)，求x0到每个点xi的最短路，

注意：若涉及区间和的问题，考虑前缀和，转化为两点之间的关系

例题：1169. 糖果

代码如下：

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
LL dist[N];
int q[N], cnt[N];
bool st[N];

/*
x = 1, A >= B && B >= A
x = 2, B >= A + 1
x = 3, A >= B
x = 4, A >= B + 1
x = 5, B >= A
*/

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool spfa()
{
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0] = 0;
    st[0] = true;
    
    while(hh != tt)
    {
        int t = q[-- tt];
        
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                
                if(cnt[j] >= n + 1) return false;
                
                if(!st[j])
                {
                    st[j] = true;
                    q[tt ++ ] = j;
                }
            }
        }
    }
    
    return true;
}

int main()
{
    scanf("%d %d", &n, &m);
    
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        if(op == 1) add(b, a, 0), add(a, b, 0);
        else if(op == 2) add(a, b, 1);
        else if(op == 3) add(b, a, 0);
        else if(op == 4) add(b, a, 1);
        else add(a, b, 0);
    }
    
    for (int i = 1; i <= n; i ++ )
        add(0, i, 1);
    
    if(!spfa()) printf("-1\n");
    else 
    {
        LL res = 0;
        for (int i = 1; i <= n; i ++ )
            res += dist[i];
        printf("%lld\n", res);
    }
    
    return 0;
}