NeFut Logo NeFut
中 Admin Login

Graph Theory Analysis and Algorithm Implementation of Difference Constraints System

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#algorithm #Graph #DP

Core Logic and Mathematical Principles

The System of Difference Constraints is a special form of linear programming consisting of $N$ variables and $M$ inequality constraints. Each inequality is of the form $x_i - x_j \le c_k$, where $c_k$ is a constant.

The core of this system lies in the isomorphism between algebraic inequalities and the triangle inequality of shortest/longest paths in graph theory.

1. Shortest Path Topological Mapping

The control equation for the shortest path in graph theory is $dist[v] \le dist[u] + w(u, v)$, which can be rearranged as:

$$dist[v] - dist[u] \le w(u, v)$$

This is mathematically consistent with the standard form of difference constraints $x_i - x_j \le c_k$. Therefore, we can transform the algebraic problem into a directed graph $G=(V, E)$:

2. Negative Cycle and No Solution Determination

The algebraic system may contain contradictory constraints (e.g., $x_1 - x_2 \le 2$ and $x_2 - x_1 \le -5$, which leads to $0 \le -3$, clearly indicating no solution). In the directed graph, this algebraic contradiction corresponds strictly to a negative weight cycle. If the graph contains a cycle with a total negative weight, the relaxation operation will loop indefinitely, causing $dist$ to approach $-\infty$. In this case, the difference constraint system has no solution. Since Dijkstra's algorithm cannot recognize negative weights and cycles, the algorithm engine here must choose SPFA.

Algorithm Derivation and State Design

Based on the constraints on unknown values (to find maximum or minimum), the graph construction scheme follows two sets of dual logic:

1. Finding Maximum Value (Strong Specification: Shortest Path)

If the problem requires finding the maximum value of $x_i - x_j$ under the premise of satisfying all inequalities, all conditions must be transformed into the standard form $x_A \le x_B + c$.

2. Finding Minimum Value (Strong Specification: Longest Path)

If the problem conditions state $x_i - x_j \ge c_k$, or require finding the minimum value under certain conditions.

3. Super Source Point Graph Construction State

If the graph may not be connected, to ensure that all variables can be traversed from the source point, a virtual super source point $x_0$ needs to be introduced. If the problem restricts all variables to be positive (i.e., $x_i \ge 1$) or non-negative (i.e., $x_i \ge 0$), directed edges from $0$ to each $i$ must be established. The edge weights depend on the direction of the constraints (shortest path connects with weight $0$, longest path connects with weight $1$ or $0$).

C++ Standard Source Code (Longest Path to Find Minimum Value + Positive Cycle Detection Template)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 100005;

struct Edge {
    int to;
    long long weight;
};

std::vector<Edge> adj[MAXN];
long long dist[MAXN];
int cnt[MAXN];     // Count of times each node is queued for cycle detection
bool in_queue[MAXN]; // Mark whether a node is currently in the queue

// SPFA to detect positive cycle and calculate longest path
bool spfa_longest(int n) {
    std::queue<int> q;

    // Initialize physical extremes
    for (int i = 0; i <= n; ++i) {
        dist[i] = -INF;
        cnt[i] = 0;
        in_queue[i] = false;
    }

    // Start from super source point 0
    dist[0] = 0;
    q.push(0);
    in_queue[0] = true;
    cnt[0] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            long long w = adj[u][i].weight;

            // Longest path relaxation equation
            if (dist[u] + w > dist[v]) {
                dist[v] = dist[u] + w;

                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                    cnt[v]++;

                    // Critical pitfall: If the count reaches or exceeds N+1 (including the super source point, a total of N+1 points), it indicates a positive cycle
                    if (cnt[v] > n) {
                        return false; // System has a positive cycle, algebraic contradiction, no solution
                    }
                }
            }
        }
    }
    return true; // Successful solution
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int opt, u, v;
        long long c;
        std::cin >> opt >> u >> v;

        // Algebraic transformation example
        if (opt == 1) { // u - v >= c  => u >= v + c
            std::cin >> c;
            adj[v].push_back(Edge{u, c});
        } else if (opt == 2) { // u - v <= c => v - u >= -c => v >= u - c
            std::cin >> c;
            adj[u].push_back(Edge{v, -c});
        } else if (opt == 3) { // u == v => u >= v + 0 and v >= u + 0
            adj[v].push_back(Edge{u, 0});
            adj[u].push_back(Edge{v, 0});
        }
    }

    // Establish super source point 0, marking implicit constraint: each variable $x_i \ge 0$, i.e., $x_i \ge x_0 + 0$
    for (int i = 1; i <= n; ++i) {
        adj[0].push_back(Edge{i, 0});
    }

    if (!spfa_longest(n)) {
        std::cout << "No Solution\n";
    } else {
        long long total_min = 0;
        for (int i = 1; i <= n; ++i) {
            total_min += dist[i];
        }
        std::cout << total_min << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

  1. Cycle Detection Threshold Not Considering Super Source Point: Difference constraint graph construction often requires introducing a virtual super source point (usually point $0$), which means the actual total number of nodes in the graph becomes $N + 1$. If the contestant's cycle termination condition is still blindly written as if (cnt[v] >= n), it will trigger premature misjudgment when the graph itself contains a complete cycle with all original nodes, incorrectly determining a valid solution as unsolvable. The standard threshold must be cnt[v] > n.
  2. Hidden Constraint Conditions Missing in Graph Construction: Many problems do not explicitly provide all variable limits. For example, if the problem implies "each person must receive at least 1 apple," this indicates an implicit constraint of $x_i \ge 1$, i.e., $x_i - x_0 \ge 1$. If these implicit constraints are missed, the various isolated connected components of the graph lack baseline calibration, leading SPFA to output unbounded extreme values (such as $-\infty$ or incorrect solutions), resulting in significant score losses in competitions.

Classic NOIP/Luogu Real Questions

1. Luogu P5960 [Template] Difference Constraint System

2. Luogu P3275 [SCOI2011] Candy

Original Source: local://10.2
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS