一题详解差分约束

补充图论知识：

• 正权边图中求最长路可使用SPFA
• 经典Dijsktra可在全负权边图中跑最长路、全正权边图中跑最短路

Dijkstra是跑不了正权值最长路的！eg：

最长路更新的话，最先出队的是1-4边，但是她不能更松弛别人，此时1-4边=3
然后1-3出队，他能松弛1-4 此时1-3为2 1-4为5
然后1-2出队，他能松弛1-3 此时1-2为1 1-3 为3
但是3不能再入队松弛别人了。
所以导致了答案错误。
想一下
为什么能跑最短路，因为路径长度不减，这是算法的核心，而到了最长路，理应是路径长度不增，但是我们看到我们确定边的过程为 3 2 5 1 3不满足单调性，所以必然错误。

所以，我们可以使用允许多次松弛的算法

---

1169. 糖果 - AcWing题库

SPFA（与dijkstra不同的是spfa是基于遍历边的思想，只要可以被更新，可能一条边会被遍历很多次，从而一个点也可能会进队和出队很多次）

判环：可以用于判断正负环，

负环（可以无限小）就正常spfa，正环（可以无限大）只需要把三角不等式换一下即可。

原理：对于一个正常的正权图而言，每个点最多被更新n-1次（最坏情况，每个点都可以把它更新），如果说是，有一个点被更新大于等于n次的话，也就是说，这里有负环。

基于 dfs 版的 SPFA 相当于是把"先进先出"的队列换成了"先进后出"的栈
也就是说，每次都以刚刚松弛过的点来松弛其他的点，如果能够松弛点 x 并且 x 还在栈中，那图中就有负环、

一般来说的话，若存在负环，那么 dfs 会比 bfs 快，因为设当前节点cnt 为 n，如果有新的push进去的点，那么下一个 cnt 一定为 n+1 了；如果是queue，队头的元素 cnt 还是 n。（stack的思想就是dfs的思想，queue的思想就是bfs的思想）
但是如果不存在负环，dfs 可能会严重影响求最短路的效率，要谨慎使用

差分约束

本质上是不等式关系和松弛原理结合的过程。

每一条路径代表着一条不等式链。

做题思路：

1. 确定求最小值 ——> 最长路；最大值——>最短路。可以根据题意也可以根据c的位置。
2. 不等式 x0 <= x1 + c，因为建边要保证c为正，所以，c为正的一侧为起点，即x1——>x0
3. 知道起点终点，也就知道是求最小值还是最大值，跑最短路还是最长路。
4. 格外注意求最值的时候提取隐藏条件，比如所有的xi 都满足 xi <= c （c为某个值），将这个条件抽象成 xi <= x0 + c,x0位超级源点，建图加上所有x0到xi的长度为c的边。答案就是从x0跑一遍最短路。

举例  

      x[i] ≥ 5
      x[i] ≥ 2
      x[i] ≥ 3
      min(x[i]) = 5

总共最小值 = min(x[i]最小值) for i in range(n)
           = 求x[i]所有下界的最大值
           = 求所有从0→i的路径和的最大值
           = 最长路求dist[i]
0 → 1 → 3 → 5 → ... → i
c1  c3  c5       ci-1
    x[1] ≥ x[0] + c[1] 
    x[3] ≥ x[1] + c[3] 
    x[5] ≥ x[3] + c[5]
    ...
    x[i] ≥ x[i-1] + c[i-1]
    则
    x[i] ≥ x[i-1] + c[i] 
         ≥ x[i-3] + c[i-3] + c[i]
         ...
         ≥ x[0] + c[1] + c[3] + c[i-3] + c[i-1]
 ⭐可以发现Σc[i]就是从0→i的一条路径的长度

    那么 求x[i]最小值
            <=>
        求所有下界的最大值
            <=>
        求所有从0→i的路径和的最大值
            <=>
        最长路求dist[i]

同理：

求x[i]最大值
            <=>
        求所有上界的最小值
            <=>
        求所有从0→i的路径和的最小值
            <=>
        最短路求dist[i]

#include
typedef long long ll;
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
int h[N], ne[M], e[M], w[M], idx;
int cnt[N];
int n, m;
int dis[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()
{
    memset(dis, -0x3f, sizeof dis);
    stack<int> q; // 对于某些负环题目的优化
    q.push(0);
    st[0] = 1;
    dis[0] = 0;
    while(q.size())
    {
        int u = q.top();
        q.pop();
        st[u] = 0;
        for (int i = h[u]; ~ i; i = ne[i])
        {
            int j = e[i];
            if(dis[j] < dis[u] + w[i]) {
                dis[j] = dis[u] + w[i];
                cnt[j] = cnt[u] + 1;
                if(cnt[j] >= n + 1) return true;
                if(!st[j]) {
                    q.push(j);
                    st[j] = 1;
                }
            }
        }
    }
    return false;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1, a, b, op; i <= m; i ++ )
    {
        cin >> op >> a >> b; // 根据不等式关系，建边
        if(op == 1) add(a, b, 0), add(b, a, 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()) cout << "-1" << '\n';
    else {
        ll ans = 0;
        for (int i = 1; i <= n; i ++ ) ans += dis[i]; 
        cout << ans << '\n';
    }
    return 0;
}