• 差分约束做法

    文章目录

    差分约束

    这是个比较偏数学的方面，可能要在纸上写很多不等书

    可用方面

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

    求不等式的可行解

    有许多个不等式组，每个不等式组形如
    在这里插入图片描述
    差分约束可以求这样一个不等式的一组可行解

    如
    在这里插入图片描述
    然后我们想一下最短路，就发现，哇，根最短路真像
    在这里插入图片描述
    就是如果给我们一个图的话，我们可以把每条边看成是一个不等式，那么在这个图上，求每个点到源点的一个最短距离，求完之后，每个点都满足这个不等式，也就是任何一个最短路问题都是一个差分约束的问题，反过来也一样
    在这里插入图片描述
    不等式就可以看作，从i走到j，长度是 c k c_k ck​的一条边，然后在图上随便选一个起点，然后跑一下最短路，求完之后必然满足条件
    因此求可行解的时候，就是把每一个不等式，转化成一条边，然后在这个图上求单元最短路径，求完之后就必然满足所有的限制条件，也就可以得到一个可行解

    源点需要满足：从源点出发，一定可以走到所有的边

    如果存在负环的话，对应到不等式就是无解，就可以推出来，比如 x i x_i xi​ < x i x_i xi​这种不成立的结论

    步骤：
    在这里插入图片描述
    同样也可以用最长路，证法相同，这里无解等于正环

    如何求最小值或者最大值

    在这里插入图片描述
    举个例子，如下图
    在这里插入图片描述

    例题

    糖果

    糖果
    第一步，条件转化

    思路

    在这里插入图片描述
    第二步，上面是找到绝对值，上面的都是相对关系，要找到一个绝对关系

    比如知道x >= 1，就可以找到0号点，写成x0 = 0，建边，也就是x >= x0 + 1

    代码

    首先上一个TLE的做法，这个题vector存图会T，但是也已经过了很多了，所以对于蓝桥杯够用

    #pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include
using namespace std;
#define endl '\n'
#define x first
#define y second
#define int long long
#define PII pair<int, int>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e5 + 10;
int n, m;
vector<PII> v[N];
int dist[N], q[N];
int cnt[N];
bool st[N];

bool spfa()
{
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    q[0] = 0;
    st[0] = true;

    while (hh != tt)
    {
        int t = q[ -- tt];
        st[t] = false;
        
        for(auto i : v[t])
        {
            if(dist[i.x] < dist[t] + i.y)
            {
                dist[i.x] = dist[t] + i.y;
                cnt[i.x] = cnt[t] + 1;
                if(cnt[i.x] >= n + 1) return 0;
                if(!st[i.x])
                {
                    q[tt ++ ] = i.x;
                    st[i.x] = 1;
                }
            }
        }
    }
    return true;
}

signed main()
{
    fast;
    cin >> n >> m;
    int a, b, x;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> x >> a >> b;
        if(x == 1) v[a].push_back({b, 0}), v[b].push_back({a, 0});
        else if(x == 2) v[a].push_back({b, 1});
        else if(x == 3) v[b].push_back({a, 0});
        else if(x == 4) v[b].push_back({a, 1});
        else v[a].push_back({b, 0});
    }
    
    for (int i = 1; i <= n; i ++ ) v[0].push_back({i, 1});
    
    if(!spfa()) cout << -1 << endl;
    else
    {
        int res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        
        cout << res << endl;
    }
    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

    这是AC代码

    #include 
#include 
#include 
#include 

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];

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

bool spfa()
{
    int hh = 0, tt = 1;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    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])
                {
                    q[tt ++ ] = j;
                    st[j] = true;
                }
            }
        }
    }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int x, a, b;
        scanf("%d%d%d", &x, &a, &b);
        if (x == 1) add(b, a, 0), add(a, b, 0);
        else if (x == 2) add(a, b, 1);
        else if (x == 3) add(b, a, 0);
        else if (x == 4) add(b, a, 1);
        else add(a, b, 0);
    }

    for (int i = 1; i <= n; i ++ ) add(0, i, 1);

    if (!spfa()) puts("-1");
    else
    {
        LL res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        printf("%lld\n", res);
    }

    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

    区间

    区间
    首先是要用到前缀和，所以0这个位置要空出来，但是还要用到超级源点，所以所以让所有的下标往后一个

    1.找不等式关系
    在这里插入图片描述
    找出来之后要想一下条件够不够，也就是是不是只要满足这些条件的任意一组解，就一定是答案？
    首先，满足前两个条件就意味着，前一个数，要么选0个要么选一个，就一定合法，满足第三个条件就一定符合要求
    条件够了就看看源点是不是符合要求

    代码

    #include
using namespace std;
#define x first
#define y second
#define endl '\n'
#define int long long
#define PII pair<int, int>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 5e4 + 10;

vector<PII> v[N];
int dist[N], n;
bool st[N];

void spfa()
{
    queue<int> q;
    memset(dist, -0x3f, sizeof dist);
    st[0] = 1; dist[0] = 0;
    q.push(0);
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for(auto i : v[t])
        if(dist[i.x] < dist[t] + i.y)
        {
            dist[i.x] = dist[t] + i.y;
            if(!st[i.x])
            {
                q.push(i.x);
                st[i.x] = 1;
            }
        }
    }
}
signed main()
{
    cin >> n;
    int a, b, c;
    for (int i = 1; i <= 50001; i ++ )
    {
        v[i - 1].push_back({i, 0});
        v[i].push_back({i - 1, -1});
    }
    
    while (n -- )
    {
        cin >> a >> b >> c;
        a ++, b ++;
        v[a - 1].push_back({b, c});
    }
    
    spfa();
    
    cout << dist[50001] << endl;
    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

    排队布局

    排队布局

    思路

    在这里插入图片描述
    上面就是所有的不等式，至于怎么找源点，我们可以假定所有的点都在0的左边，这样，x[i] > x[i - 1]，就可以连起来所有的点，从0到所有点连一个长度是0的边

    第二问能不能无限大，其实是跑一个最短路，看看是不是INF（也就是1和n直接没有限制）

    第一问判断有无负环，第二问我们先让x1等于0，因为让求的是个相对关系，所以可以任取，然后跑一下最短路，如果等于INF就是无限制，否则存的就是值

    这里的虚拟源点不需要真正的建出来，只需要体现出来就ok

    代码

    #include
using namespace std;
#define x first
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define y second
#define endl '\n'
#define int long long
#define PII pair<int, int>
#define INF 0x3f3f3f3f3f3f3f3f
const int N = 1010;

int n, m1, m2;
int cnt[N], dist[N];
bool st[N];
vector<PII> v[N];

bool spfa(int size)
{
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    queue<int> q;
    for (int i = 1; i <= size; i ++ )
    {
        dist[i] = 0;
        q.push(i);
        st[i] = 1;
    }
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = 0;
        for(auto i : v[t])
        {
            if(dist[i.x] > dist[t] + i.y)
            {
                cnt[i.x] = cnt[t] + 1;
                dist[i.x] = dist[t] + i.y;
                if(cnt[i.x] >= n) return 0;
                if(!st[i.x])
                {
                    q.push(i.x);
                    st[i.x] = 1;
                }
            }
        }
    }
    return 1;
}

signed main()
{
    fast;
    cin >> n >> m1 >> m2;
    
    for (int i = 1; i < n; i ++ ) v[i+1].push_back({i, 0});
    while(m1 --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(b < a) swap(a, b);
        v[a].push_back({b, c});
    }
    while(m2 --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if(b < a) swap(a, b);
        v[b].push_back({a, -c});
    }
    
    if(!spfa(n)) cout << -1 << endl;
    else
    {
        spfa(1);
        if(dist[n] == INF) cout << -2 << endl;
        else cout << dist[n] << endl;
    }
    
    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

    雇佣收银员

    雇佣收银员

    思路

    用num[i]表示第i点来的人数，xi表示从num[i]中选的人数

    要满足的条件为
    在这里插入图片描述
    因为是一段区间和，也就可以用前缀和来做，要把第0位空出来
    得到了
    在这里插入图片描述
    再化简一下
    在这里插入图片描述
    但是这里的第四个不符合形式，就可以把s24不当作变量，枚举s24的所有取值，从小到大枚举，找到第一个s24的值，使得这个问题有解，这个问题本来答案就是s24，当枚举完任意一个都是无解的，说明就是无解的

    一共24个点，三大组，一共七十多条边，枚举一千次是可以的
    根据第一个条件，0号点可以作为超级源点，遍历所有的边，也就是超级源点

    #pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define PII pair<int, int>
#define x first
#define y second
#define endl '\n'
#define vi vector 
#define pb push_back 
const int N = 30;
int n;
vi<PII> v[N];
int dist[N], cnt[N], r[N], num[N];
bool st[N];

void add(int u, int a, int b){
    v[u].pb({a, b});
}

void build(int c)
{
    for(int i=0; i<=24; i++) v[i].clear();
    v[0].pb({24, c});//体现s24是个定值，s24 <= s0 + c
    v[24].pb({0, -c});
    for (int i = 1; i <= 7; i ++ ) v[i + 16].pb({i, r[i] - c}) ;
    for (int i = 8; i <= 24; i ++ ) v[i - 8].pb({i, r[i]});
    for (int i = 1; i <= 24; i ++ )
    {
        v[i].pb({i - 1, - num[i]});
        v[i - 1].pb({i, 0});
    }
}

bool spfa(int s24)
{
    build(s24);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);
    memset(dist, -0x3f, sizeof dist);
    
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    st[0] = 1;
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        
        for(auto i : v[t])
        {
            if(dist[i.x] < dist[t] + i.y)
            {
                dist[i.x] = dist[t] + i.y;
                cnt[i.x] = cnt[t] + 1;
                if(cnt[i.x] >= 25) return 0;
                if(!st[i.x])
                {
                    q.push(i.x);
                    st[i.x] = 1;
                }
            }
        }
    }
    return 1;
}

void work()
{
    for (int i = 1; i <= 24; i ++ ) cin >> r[i];
    cin >> n;
    memset(num, 0, sizeof num);
    for (int i = 1; i <= n; i ++ )
    {
        int t;
        cin >> t;
        num[t + 1] ++;
    }
    
    bool flag = 0;
    for (int i = 0; i <= 1000; i ++ )
        if(spfa(i))
        {
            cout << i << endl;
            flag = 1;
            break;
        }
    
    if(!flag) cout << "No Solution" << endl;
}
signed main()
{
    fast;
    int _ = 1;
    cin >> _;
    while(_ --) work();
}

    • 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

    总结：
    如何看出来一个题是差分约束问题，本质上就是看一下是不是可以由一堆不等式给出来，用一堆不等式限制出来，是不是形如
    在这里插入图片描述
    这样的关系，最难就是看出来是图论，然后建图

    在想差分问题的时候，如果想不清楚的话，只要抓住一点核心就可以，给了一个不等式组之后，如果想求一个最大值(最小值)的话，其实就是看一下这个数，比如xi，在所有的不等式组中，能构成的链式法则里面（一定是从xi开始最后走到某一个定值）如图
    在这里插入图片描述
    要求最大值，实际上就是看一下，能构成的链式法则中上界是什么，要求的就是所有上届的最小值。
    如果求的话，就可以发现，把所有的不等式变成边之后，每一个上界都可以对应一个从起点到i的路径，起点就是我们固定值的点，如果要求所有上界的最小值的话，其实就是求所有路径的最小值

  • 相关阅读:
    应该选择低代码还是零代码？
    2024暑期实习八股笔记
    MindFusion Crack版,以围绕根的同心圆排列层
    armbian 安裝配置教程
    极智AI | 讲解 TensorRT 显式batch 和 隐式batch
    Pytorch量化感知训练
    flutter 数组筛查功能实现
    数据结构学习笔记（二）——栈和队列
    【uniapp小程序】路由跳转navigator传参封装
    Jenkins Jenkinsfile管理 Pipeline script from SCM
  • 原文地址：https://blog.csdn.net/weixin_51176105/article/details/126188183