Graph Theory Analysis and Algorithm Implementation of Dif...

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)$:

Each variable $x_i$ is mapped to a vertex $V_i$ in the graph.
Each constraint $x_i - x_j \le c_k$ is transformed into $x_i \le x_j + c_k$, which maps to a directed edge $e(j, i)$ from node $j$ to node $i$ with a weight of $c_k$.

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$.

State Derivation: Since $x_i \le x_j + c_1$ and $x_i \le x_k + c_2$, to satisfy all upper bound constraints, $x_i$ must ultimately be limited by the minimum value among all path combinations. In other words, globally, $x_i - x_j \le \text{dist}(j, i)$.
Conclusion: Use shortest path algorithm to find maximum value.

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.

State Derivation: Transform all inequalities into standard lower bound forms: $x_i \ge x_j + c_k$.
Longest Path Triangle Inequality: $dist[v] \ge dist[u] + w(u, v) \implies dist[v] - dist[u] \ge w(u, v)$.
Conclusion: Use longest path algorithm to find minimum value (initialize $dist$ to $-\infty$, and change the relaxation condition to if (dist[u] + w > dist[v])). In this case, the algebraic feature of no solution corresponds to a positive weight cycle in the graph.

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 实战避坑指南

环路判定阈值未考虑超级源点： 差分约束建图通常需要引入虚拟超级源点（通常为 $0$ 号点），这意味着整个图的实际节点总数变为了 $N + 1$。如果选手的环路终止判定条件依然盲目写成 if (cnt[v] >= n)，在图本身是一个包含了所有原节点的完整大环时，会触发提前误判，将合法解判定为无解。标准阈值必须是 cnt[v] > n。
隐藏约束条件漏建图： 许多题目不会显式给出所有变量的界限。例如题目暗示“每个人至少分到 1 个苹果”，这意味着隐含了约束 $x_i \ge 1$，即 $x_i - x_0 \ge 1$。如果漏掉了这些隐含约束，图的各个孤立连通块没有底座标定，SPFA 跑出的结果将是无约束的极值（如 $-\infty$ 或错解），在赛场上会直接痛失绝大部分分数。

经典 NOIP/洛谷真题

1. 洛谷 P5960 【模板】差分约束系统

题意描述： 给定一个包含 $N$ 个变量和 $M$ 个不等式的系统，每个不等式形如 $x_{c_1} - x_{c_2} \le y$。求一组可行解，使得所有不等式同时满足。如果无解输出 NO。
问题本质与核心思路： 标准最短路差分约束模板。将 $x_{c_1} - x_{c_2} \le y$ 转换为标准型 $x_{c_1} \le x_{c_2} + y$，从 $c_2$ 向 $c_1$ 连一条权值为 $y$ 的有向边。由于是求可行解，任选最短路或最长路均可。建立超级源点 $0$ 向各个点连权值为 $0$ 的边，跑一次标准 SPFA 最短路。若检测到负环则输出 NO；否则，最终的 $dist[i]$ 向量本身就是一组完全合法的代数解。

2. 洛谷 P3275 [SCOI2011] 糖果

题意描述： 幼儿园有 $N$ 个小朋友，老师要分糖果。有 $M$ 个限制条件，形如：“A 必须比 B 多”、“A 不能比 B 少”等。每个小朋友至少要分到 1 个糖果。求老师至少需要准备多少个糖果。如果无法满足则输出 -1。
问题本质与核心思路： 最长路差分约束的硬核变形题。求“至少”需要多少糖果，本质是求代数系统的最小值，因此整体采用最长路建图。条件拆解：“A不能比B少”即 $x_A \ge x_B$，连边 $B \to A$，权值为 0；“A必须比B多”即 $x_A \ge x_B + 1$，连边 $B \to A$，权值为 1。隐含条件：每个小朋友至少 1 个糖果，即 $x_i \ge 1$，由超级源点 $0$ 向所有点 $i$ 连一条权值为 1 的边。利用 SPFA 跑最长路，若发现正环则说明条件冲突，输出 -1。否则，$\sum_{i=1}^N dist[i]$ 即为最终答案。注意，糖果总数极易超过 int 范围，必须强制使用 long long 累加。

Graph Theory Analysis and Algorithm Implementation of Difference Constraints System