差分约束系统

// 差分约束：求 x[n] - x[1] 的最大值
// 约束：x[b] - x[a] <= c
public boolean solve(int n, int[][] constraints) {
    // 建图
    List<int[]>[] adj = new ArrayList[n + 1];
    for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();

    for (int[] con : constraints) {
        int a = con[0], b = con[1], c = con[2];
        adj[a].add(new int[]{b, c}); // a → b, 权 c
    }

    // 超级源点 0 → 所有点，权 0（保证连通）
    for (int i = 1; i <= n; i++) {
        adj[0].add(new int[]{i, 0});
    }

    // Bellman-Ford / SPFA 判负环
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE / 2);
    dist[0] = 0;

    for (int round = 0; round <= n; round++) {
        boolean updated = false;
        for (int u = 0; u <= n; u++) {
            if (dist[u] == Integer.MAX_VALUE / 2) continue;
            for (int[] edge : adj[u]) {
                int v = edge[0], w = edge[1];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    updated = true;
                    if (round == n) return false; // 负环 → 无解
                }
            }
        }
        if (!updated) break;
    }
    return true; // dist[] 是一组解
}

boolean spfa(int n, List<int[]>[] adj) {
    int[] dist = new int[n + 1];
    int[] count = new int[n + 1]; // 入队次数
    boolean[] inQueue = new boolean[n + 1];
    Queue<Integer> q = new LinkedList<>();

    q.offer(0); inQueue[0] = true;
    while (!q.isEmpty()) {
        int u = q.poll(); inQueue[u] = false;
        for (int[] edge : adj[u]) {
            int v = edge[0], w = edge[1];
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                count[v]++;
                if (count[v] > n) return false; // 负环
                if (!inQueue[v]) { q.offer(v); inQueue[v] = true; }
            }
        }
    }
    return true;
}