【夯实算法基础】差分约束

简介: 【夯实算法基础】差分约束

@[toc]

差分约束

差分约束的两个应用

求不等式组的可行解

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

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

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

:neutral_face: 步骤3:从源点走一遍单源最短路

如下图所示,如果存在负环:

image-20220805105904262

:ghost: 步骤4:求完单源最短路之后

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

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

结论:如果求的是最小值,则应该求最长路;如果求的是最大值,则应该求最短路

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

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

求最大值

求所有从x出发,构成的多个形如以下的不等式链:

$$ xi≤xj+c1≤xk+c2+c1≤⋅⋅⋅≤x0+c1+c2+⋅⋅⋅+cm(x0=0) $$

所计算出来的上界,最终x[i]的值等于所有上界的最小值

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

image-20220805125324553

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

xi最小值 时则完全相反,求一个形如如下不等式链所计算出的下界,最终在所有下界里取最大值

$$ xi≥xj+c1≥xk+c2+c1≥⋅⋅⋅≥x0+c1+c2+⋅⋅⋅+cm(x0=0) $$

转换成图论的问题,就是求 dist[i]最大值,即最长路求解

例题

AC1169 糖果

:jack_o_lantern: 题目

image-20220805125749279

:rainbow: 思路

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

  • 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次),即发现负环

:horse: 代码

#include <bits/stdc++.h>
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;
}

还有一种方法可以求

:wedding: 思路:tarjan

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

:cactus: 代码

#include <bits/stdc++.h>
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;
}

AcWing 362. 区间

:ocean:题目

在这里插入图片描述

:cactus:思路:差分约束

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

对于本题中我们需要满足一个区间内填的整数和不超过某个数,那么可以用前缀和的思想。因为前缀和中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,... 一直可以走到终点

:rabbit2: 代码

#include <bits/stdc++.h>
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;
}

AC1170. 排队布局

:joy: 题目
在这里插入图片描述

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

  • 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

:dango: 代码

#include <bits/stdc++.h>
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;
}

AcWing 393. 雇佣收银员

:first_quarter_moon_with_face: 题目

在这里插入图片描述

:dagger: 思路

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 <bits/stdc++.h>
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;
}

:lollipop: 有疑问欢迎评论区留言哦

image-20220729114611343

相关文章
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
4月前
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
50 4
【算法】前缀和与差分
|
6月前
|
算法 C++
c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
|
6月前
|
人工智能 算法 BI
【算法基础】基础算法(二)--(高精度、前缀和、差分)(下)
【算法基础】基础算法(二)--(高精度、前缀和、差分)(下)
|
6月前
|
存储 算法 索引
【算法基础】基础算法(二)--(高精度、前缀和、差分)(上)
【算法基础】基础算法(二)--(高精度、前缀和、差分)(上)
|
6月前
|
算法
R语言使用随机技术差分进化算法优化的Nelson-Siegel-Svensson模型
R语言使用随机技术差分进化算法优化的Nelson-Siegel-Svensson模型
|
6月前
|
人工智能 移动开发 算法
算法基础:前缀和与差分
算法基础:前缀和与差分
73 1
算法基础:前缀和与差分
|
6月前
|
人工智能 算法
基础算法--前缀和与差分
基础算法--前缀和与差分
|
6月前
|
算法 测试技术 C#
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
【滑动窗口】【差分数组】C++算法:K 连续位的最小翻转次数
|
12月前
|
算法
算法学习--前缀和与差分
算法学习--前缀和与差分