差分约束

差分约束的两个应用

求不等式组的可行解

⛵️步骤1：把每个x[i] <= x[j] + c[k]这样的不等式转化为一条从x[j]走到x[i]长度为c[k]的边。

🌖步骤2：然后在这个图上找一个超级源点，使得该源点一定可以遍历到所有边

源点需要满足的条件：从源点出发，一定可以走到所有的边，否则如果有一条边走不到的话，那么就无法确定两个点的约束条件。若一个点走不到无所谓，因为它不受任何约束。

😐 步骤3：从源点走一遍单源最短路

如下图所示，如果存在负环：

👻 步骤4：求完单源最短路之后：

结果1：如果存在负环，则原不等式组一定无解
结果2：如果没有负环，则 dist[i]就是原不等式组的一个可行解

如何求最大值或者最小值，这里的最值指的是每个变量的最值

结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。

问题：如何转化 xi≤c，其中 c 是一个常数，这类的不等式。

方法：建立一个超级源点0，然后建立 0 -> i 的边，长度是 c 即可。

求最大值：

求所有从x出发，构成的多个形如以下的不等式链：
$$xi\le xj+c1\le xk+c2+c1\le \cdot \cdot \cdot \le x0+c1+c2+\cdot \cdot \cdot +cm(x0=0)$$
所计算出来的上界，最终x[i]的值等于所有上界的最小值。

这里所有上界的最小值可以理解这么一个例子：

把上述转换成图论的问题，就是求 dist[i] 的最小值，即最短路求解

求 xi 的最小值 时则完全相反，求一个形如如下不等式链所计算出的下界，最终在所有下界里取最大值
$$xi\ge xj+c1\ge xk+c2+c1\ge \cdot \cdot \cdot \ge x0+c1+c2+\cdot \cdot \cdot +cm(x0=0)$$
转换成图论的问题，就是求 dist[i]的最大值，即最长路求解

例题

AC1169 糖果

🎃 题目：

🌈 思路

本道题求的是最小值，所以也就是求最长路，其中最关键的就是如何建图：

• x == 1，A == B ，A >= B -> A >= B + 0, A <= B -> B >= A + 0
• x == 2，A < B -> B >= A + 1
• x == 3, A >= B -> A >= B + 0
• x == 4，A > B -> A >= B + 1
• x == 5, A <= B -> B >= A + 0

由于本题中可能存在正环，所以我们需要用spfa来求最长路，这里用一个不会TLE的判负环方法，那就是把SPFA算法中的循环队列改为栈，这样对于遇到的负环，就不会加入队尾，知道再次遍历完整个队列才去算他。遇到负环会直接在栈顶连续入栈出栈，直到判断他的cnt[i] >= n+1(因为多了一个0号点，所以有n+1个点，一个点最多只能更新n次)，即发现负环

🐴 **代码 **

#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int dist[N];
int cnt[N];
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa()
{
    mset(dist, -0x3f);
    dist[0] = 0;
    stack<int> q;
    q.push(0);
    st[0] = 1;
    while (q.size())
    {
        int t = q.top();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; 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])
                {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return true;
}
void solve()
{
    mset(h, -1);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1)
        {
            add(a, b, 0);
            add(b, a, 0);
        }
        else if (t == 2)
            add(a, b, 1);
        else if (t == 3)
            add(b, a, 0);
        else if (t == 4)
            add(b, a, 1);
        else
            add(a, b, 0);
    }
    for (int i = 1; i <= n; i++)
        add(0, i, 1);
    bool ok = spfa();
    if (ok)
    {
        ll ans = 0;
        for (int i = 1; i <= n; i++)
            ans += dist[i];
        cout << ans;
    }
    else
        cout << -1;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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
107
108
109

还有一种方法可以求

💒 思路：tarjan

我们可以求出每一个强连通分量，然后进行缩点，如果发现有正环就表示无解。tarjan算法是可以保证 O(n+m)的，所以用这个算法求一定不会卡。

🌵 **代码 **

#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 6, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int dist[N];
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int Size[N];
int id[N];
int scc_cnt;
int h[N], hs[N], e[M], w[M], ne[M], idx;
void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u])
    {
        scc_cnt++;
        int y;
        do
        {
            y = stk[top--];
            id[y] = scc_cnt;
            Size[scc_cnt]++;
            in_stk[y] = false;
        } while (y != u);
    }
}
void solve()
{
    mset(h, -1);
    mset(hs, -1);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1)
        {
            add(h, a, b, 0);
            add(h, b, a, 0);
        }
        else if (t == 2)
            add(h, a, b, 1);
        else if (t == 3)
            add(h, b, a, 0);
        else if (t == 4)
            add(h, b, a, 1);
        else
            add(h, a, b, 0);
    }
    for (int i = 1; i <= n; i++)
        add(h, 0, i, 1);
    tarjan(0);
    bool ok = false; //判断是否存在正环
    for (int i = 0; i <= n; i++)
    {
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i];
            int b = id[k];
            if (a == b)
            {
                if (w[j] > 0)
                {
                    ok = true;
                    break;
                }
            }
            else
            {
                add(hs, a, b, w[j]);
            }
        }
    }
    if (ok)
    {
        puts("-1");
        return;
    }
    for (int i = scc_cnt; i >= 1; i--)
    {
        for (int j = hs[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            dist[k] = max(dist[i] + w[j], dist[k]);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= scc_cnt; i++)
        ans += (ll)Size[i] * dist[i];
    cout << ans;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

AcWing 362. 区间

🌊**题目 **

🌵思路：差分约束

本题保证是一定有解的，我们可以将区间上的每一个点都填上。

对于本题中我们需要满足一个区间内填的整数和不超过某个数，那么可以用前缀和的思想。因为前缀和中s[0] =0,所以需要将整个区间都加上1，这样区间范围就由[0,50000] -> [1, 50001],最后结果是不变的。

我们用s[i]来表示1~i中选了多少个数，我们要求就是s[50001]的最小值，所以我们需要求最长路。

对于S，S需要满足如下条件：

1. s[i] >= s[i-1]
2. s[i] - s[i-1] <= 1==> s[i-1] >= s[i] - 1
3. 区间[a,b]内至少有c个数，==》 s[b] - s[a - 1] >= c ==> s[b] >= s[a-1] + c

这里我们的0号点就是超级源点，它可以到1，1到2，… 一直可以走到终点

🐇 **代码 **

#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n, m;
int dist[N];
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa()
{
    mset(dist, -0x3f);
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    st[0] = 1;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return true;
}
void solve()
{
    mset(h, -1);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int c, a, b;
        cin >> a >> b >> c;
        a++;
        b++;
        add(a - 1, b, c);
    }
    for (int i = 1; i <= 5e4 + 1; i++)
    {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }

    spfa();
    cout << dist[50001];
    return;
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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

AC1170. 排队布局

😂 题目

本题是让我们求最大值，所以是求最短路。

• B - A <= L <==> B <= A + L
• B - A >= D <==> A <= B - D
• s[i] - s[i-1] >= 0 <==> s[i - 1] <= s[i] + 0 两头牛之间的距离至少是0

我们要求的答案：

• 不存在满足要求的方案 <==> 有负环 ：输出-1
• 距离无穷大：输出-2
• 有最短路：输出

如何判断负环，上糖果那道题一样，设置一个超级源点跑一遍最短路看入队次数是否超过n

🍡 ** 代码**

#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n, m1, m2;
int dist[N];
int cnt[N];
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool spfa(int s)
{
    mset(dist, 0x3f);
    mset(cnt, 0);
    mset(st, 0);
    stack<int> q;
    for (int i = 1; i <= s; i++)
    {
        q.push(i);
        dist[i] = 0;
        st[i] = 1;
    }
    while (q.size())
    {
        int t = q.top();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; 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)
                    return false;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return true;
}
void solve()
{
    mset(h, -1);
    cin >> n >> m1 >> m2;
    for (int i = 1; i < n; i++)
        add(i + 1, i, 0);
    while (m1--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    while (m2--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(b, a, -c);
    }
    // 先判断是否出现了负环
    if (!spfa(n))
    {
        cout << -1;
    }
    else
    {
        spfa(1);
        if (dist[n] == inf)
            cout << -2;
        else
            cout << dist[n];
    }
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    while (T--)
        solve();
    return 0;
}
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
107
108
109
110
111

AcWing 393. 雇佣收银员

🌛 题目

🗡 **思路 **

r[i] 表示i时刻来了多少顾客

nums[i]表示i`时刻最多有多少个收银员

x[i]表示i时刻选择了多少个收银员

我们可以列出不等式：

• 0<=x[i]<=nums[i]

• x[i-7] + x[i-6] + ... x[i] >= r[i] ：一个收银员可以工作8个小时，一个顾客可以被在i时刻来了那么它就可以被[i-7,i]这段时间内开始工作的收银员服务。

这里我们可以用前缀和的思想，用s[i]表示[1, i]这一时间段内总共来了多少个收银员，那么上面的不等式就可以转换为：

• 0 <= s[i] - s[i - 1] <= nums[i]
• s[i] - s[i - 8] >= r[i]

这里我们需要注意一个细节，如果一个服务员是在20点上的班，那么它可以工作到早上3点。所以这里我们需要分别判断

• i >= 8 : s[i] - s[i - 8] >= r[i]
• i < 8 : s[i] + s[24] - s[i + 16] >= r[i]

我们可以发现，i<8的不等式中有三个变量，我们又要求s[24]，所以我们可以枚举s[24]的值，找到符合所有不等式的最小值即可。

#include 
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
#define endl '\n'
#define ppb pop_back
#define pb push_back
#define pf push_front
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof(x))
#define rep(i, l, r) for (LL i = l; i <= (r); ++i)
#define per(i, r, l) for (LL i = r; i >= (l); --i)
const int N = 1e5 + 10, M = N * 3, inf = 0x3f3f3f3f, mod = 998244353;
int n;
int dist[N];
int cnt[N];
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int r[N];
int num[N];
int q[N];
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void build(int c)
{
    mset(h, -1);
    idx = 0;
    for (int i = 1; i <= 24; i++)
    {
        add(i - 1, i, 0);
        add(i, i - 1, -num[i]);
    }
    for (int i = 8; i <= 24; i++)
        add(i - 8, i, r[i]);
    for (int i = 1; i < 8; i++)
    {
        add(i + 16, i, -c + r[i]);
    }
    // s24 == c
    add(0, 24, c);
    add(24, 0, -c);
}
bool spfa(int c)
{
    build(c);
    // 求最长路
    mset(dist, -0x3f);
    mset(cnt, 0);
    mset(st, 0);
    stack<int> q;
    q.push(0);
    dist[0] = 0;
    st[0] = 1;
    while (q.size())
    {
        int t = q.top();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; 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] >= 25)
                    return false;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return true;
}
void solve()
{
    mset(num, 0);
    for (int i = 1; i <= 24; i++)
        cin >> r[i];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        num[x + 1]++;
    }
    int l = 0, r = n;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (spfa(mid))
            r = mid;
        else
            l = mid + 1;
    }
    if (!spfa(r))
        cout << "No Solution\n";
    else
        cout << r << '\n';
}
signed main()
{
#ifdef Xin
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

🍭 有疑问欢迎评论区留言哦