Some updates

Update 2021/11/16: it is found that there are serious errors in the previous conclusions, which have been corrected. If any readers are misled, we apologize.

1. Preface

Differential constraint is a shortest path algorithm, which is specially used to solve the following problems:

Given \ (n \) positive integers \ (x_1,x_2,...,x_n \) and \ (m \) inequalities in the form of \ (x_i-x_j \leq k,k \in Z \), ask whether there is a set of solutions so that \ (x_1,...,x_n \) satisfies the above inequalities and find any set of solutions.

Pre knowledge: SPFA.

2. Detailed explanation

Example: P5960 [template] differential constraint algorithm

At first glance, you may have no clue: what does this have to do with the shortest circuit?

But in fact, let's make a slight deformation of the formula \ (x_i-x_j \leq k \):

Compare the formula we often use in the shortest path:

You will find that the two formulas actually look very similar.

Some people will ask: isn't our general transfer formula \ (dis_ \ GEQ dis_j + val \)? Why is the less than or equal sign instead of the greater than or equal sign?

The reason is very simple, because the requirements of the first formula must be met, and the second formula must also be met after finding the shortest circuit (otherwise it is not the shortest circuit).

And \ (dis_ \ GEQ dis_j + val \) essentially means that the shortest path has not been found at this time and needs to be transferred.

Therefore, the less than or equal sign is adopted.

Therefore, if we regard \ (x_i \) as \ (dis_i \) and \ (k \) as \ (val \), we can do this:

First, for each formula \ (x_i-x_j \leq k \), connect an edge from \ (J \) to \ (I \).

Then establish a super starting point 0, and connect an edge with an edge weight of 0 to all points.

This is done to facilitate the shortest path.

It should be noted that in different problems, the edge weight is not necessarily 0, and specific problems need to be analyzed.

Then find the shortest path again. At this time, all \ (dis_i \) should meet the inequality given in the original problem.

Then \ (\ {dis \} \) is a set of solutions that meet the conditions.

Of course, all \ (dis_i \) can be added with any constant \ (k \) at the same time. Anyway, the difference is eliminated after doing it.

So when is there no solution?

No solution: a negative ring appears in the graph, which indicates that several inequalities cannot be established at the same time.

Special reminder: dijkstra cannot be used to solve differential constraint problems because it has negative weight edges.

code:

/*
========= Plozia =========
    Author:Plozia
    Problem:P5960 [Template difference constraint algorithm
    Date:2021/4/29
========= Plozia =========
*/

#include <bits/stdc++.h>
using std::queue;

typedef long long LL;
const int MAXN = 5e3 + 10;
int n, m, Head[MAXN], cnt_Edge = 1, dis[MAXN], cnt[MAXN];
struct node { int to, val, Next; } Edge[MAXN << 1];
bool book[MAXN];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
void add_Edge(int x, int y, int z) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, z, Head[x]}; Head[x] = cnt_Edge; }

void SPFA()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    memset(book, 0, sizeof(book));
    queue <int> q; q.push(0); dis[0] = 0; book[0] = 1;
    while (!q.empty())
    {
        int x = q.front(); q.pop(); book[x] = 0;
        for (int i = Head[x]; i; i = Edge[i].Next)
        {
            int u = Edge[i].to;
            if (dis[x] + Edge[i].val < dis[u])
            {
                dis[u] = dis[x] + Edge[i].val;
                if (!book[u])
                {
                    book[u] = 1; q.push(u); ++cnt[u];
                    if (cnt[u] > n) { printf("NO\n"); exit(0); }
                }
            }
        }
    }
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= m; ++i)
    {
        int y = read(), x = read(), z = read();//Notice the order of x and y here
        add_Edge(x, y, z);
    }
    for (int i = 1; i <= n; ++i) add_Edge(0, i, 0);
    SPFA();
    for (int i = 1; i <= n; ++i) printf("%d ", dis[i]);
    printf ("\n"); return 0;
}

3. Expansion

Two conclusions:

• \(x_i-x_j \leq k \leftrightarrow x_i \leq x_j+k \), this formula is very similar to the shortest triangle inequality \ (dis_i \leq dis_j+k \), so it connects the edges \ ((j,i,k) \).
  Because it is the shortest triangle inequality, the original drawing requires the shortest path.
• \(x_i-x_j \leq k \leftrightarrow x_j \geq x_i+k \), this formula is very similar to the triangle inequality \ (dis_j \geq dis_i-k \) of the longest path, so it connects the edges \ ((i,j,-k) \).
  Because it is a triangular inequality of the longest path, the original drawing requires the longest path.

In fact, the first conclusion above is the conclusion of the previous step-by-step reasoning, while the second conclusion is an analogy to the reasoning process of the first conclusion, which adopts the longest way to solve the problem.

These two conclusions are right, but when using these two conclusions, we should pay attention to one thing: the edge right must be meaningful in the topic!

for instance P3275 [SCOI2011] candy For this question, if the longest path is used, the answer is correct, but if the shortest path is used, the answer is wrong.

Why?

For example, there is \ (a-b\leq-1 \) when \ (z=2 \). If the shortest circuit is adopted, the side \ ((b,a,-1) \) needs to be connected. However, the number of candy is obviously non negative, so the side weight is meaningless, and the answer is naturally wrong.

4. Summary

The conclusions are as follows:

• \(x_i-x_j \leq k \leftrightarrow x_i \leq x_j+k \), this formula is very similar to the shortest triangle inequality \ (dis_i \leq dis_j+k \), so it connects the edges \ ((j,i,k) \).
  Because it is the shortest triangle inequality, the original drawing requires the shortest path.
• \(x_i-x_j \leq k \leftrightarrow x_j \geq x_i-k \), this formula is very similar to the triangular inequality of the longest path \ (dis_j \geq dis_i+k \), so it connects the edges \ ((i,j,-k) \).
  Because it is a triangular inequality of the longest path, the original drawing requires the longest path.