差分约束算法笔记但是只有板子因为为了应付今晚的G题所以匆匆学的

标题长，别怪我

没啥好说的，因为只有板子，直接上板子题

（小黄油美式害得我根本睡不着，浅浅写一下，哪里有问题欢迎喷我，脑子可能今晚有点不好使）

P5960 【模板】差分约束

题目描述

给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：

$\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}$

的不等式组，求任意一组满足这个不等式组的解。

对于 $100\%$ 的数据，$1\leq n,m \leq 5\times 10^3$，$-10^4\leq y\leq 10^4$，$1\leq c,c'\leq n$，$c \neq c'$。

思路

首先我们看了半天，发现整个不等式组就这种式子：

$x_i-x_j \leq c$

小学学过的移项：$x_i \leq x_j + c$

大佬们都学过bellman-ford吧，是不是想到什么了

没错，图论里的三角形不等式啊 ：

$dist[i] \leq dist[j] + c$

那不就能和图论结合了吗，我们把$x_i$看做一个编号为$i$节点，那每个约束条件不就是编号为$j$的节点对编号为$i$的节点连一条长度为$c$的有向边了吗？

那我们就可以在建好的图上跑bellman-ford了，至于用这个的原因，因为可能会有负环啊！！！

说到负环了，其实负环就代表了这个方程组无解的情况 至于为什么嘛，看这个例子：

$\begin{cases} x_1-x_2\leq 114 \\x_2-x_3 \leq -514 \\ x_3 - x_1\leq -1919810 \end{cases}$

这个例子就是对应了一个负环，跑bellman的时候你跑了半天会发现：

$x_3 \leq x_3 -1920210$

啊哈，显然无解吧

话说回来，这个图可以跑最长路也可以跑最短路，这俩正好对应了最小的一组解和最大的一组解的情况。

因为我们选边的时候可能得到两个条件，一个边权大一个边权小，我们跑最短路时肯定会取小的边权，正好就是我们求最大解时选的，那最长路正好相反了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
    int u, v, w;
}edges[5555];
int n, m;
int dist[5555];
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].v >> edges[i].u >> edges[i].w;
    }
    for (int i = 1; i <= n; i++) {
        dist[i] = 1e9;
    }
    dist[1] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dist[edges[j].v] = min(dist[edges[j].v], dist[edges[j].u] + edges[j].w);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (dist[edges[i].v] > dist[edges[i].u] + edges[i].w) {
            cout << "NO";
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dist[i] << ' ';
    }
    return 0;
}

好困啊 这个代码调了半个小时 赶紧写完这一篇洗洗睡了

今晚（准确来说现在已经第二天了）的G题

题目描述

您将得到一个整数 $N$ 和长度为 $M$ 的整数序列 $L=(L_1,L_2,\dots,L_M)$ 、 $R=(R_1,R_2,\dots,R_M)$ 和 $S=(S_1,S_2,\dots,S_M)$ 。

判断是否存在长度为$N$的正整数序列 $A$ 满足以下条件。如果存在这样一个序列，求出 $A$ 的最小可能和。

-所有 $i$ （ $1 \le i \le M$ ）的 $\displaystyle \sum_{j=L_i}^{R_i} A_j = S_i$ 。

思路

这个不就是上面对应的最长路差分约束嘛 赛后学完一发过 应该早点学的

不得不吐槽atc的cloudflare 不翻墙验证通过不了 害的浪费好久时间

首先$\displaystyle \sum_{j=L_i}^{R_i} A_j = S_i$不能直接用，我们考虑用前缀和数组$B$来替换$A$数组

所以：

对于所有$1 \leq i \leq M$，$B_{r_i} - B_{L_{i - 1}} \leq S_i$

对于所有$1 \leq j \leq N$，$1 \leq B_j - B_{j - 1}$

那不就是很裸的差分约束了么。。。

不管了 加纳 反正听别人说这个题比L5的差分约束给的例题都还要简单 上面看懂了这题也不难好吧

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int u, v;
    int w;
};
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> l(m), r(m), s(m);
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> s[i];
        int len = r[i] - l[i] + 1;
        if (s[i] < len) {
            cout << -1;
            return 0;
        }
    }
    vector<node> edges;
    for (int i = 1; i <= n; i++) {
        edges.push_back({i - 1, i, 1});
    }
    for (int i = 0; i < m; i++) {
        int u = l[i] - 1;
        int v = r[i];
        int nex = s[i];
        edges.push_back({u, v, nex});
        edges.push_back({v, u, -nex});
    }
    int v = n + 1;
    vector<int> dist(v, -1e18);
    dist[0] = 0;
    for (int i = 0; i < v - 1; i++) {
        bool flag = 0;
        for (int i = 0; i < edges.size(); i++) {
            auto nex = edges[i];
            if (dist[nex.u] != -1e18 && dist[nex.v] < dist[nex.u] + nex.w) {
                dist[nex.v] = dist[nex.u] + nex.w;
                flag = 1;
            }
        }
        if (!flag) {
            break;
        }
    }
    bool check = 0;
    for (int i = 0; i < edges.size(); i++) {
        auto nex = edges[i];
        if (dist[nex.u] != -1e18 && dist[nex.v] < dist[nex.u] + nex.w) {
            check = 1;
            break;
        }
    }
    if (check) {
        cout << -1;
    } else {
        cout << dist[n];
    }
    return 0;
}

写完了，现在是0:48:52，咖啡消耗完了 洗洗睡咯，明早（准确来说是今天）还要早起跑步