여러 개의 선형 부등식으로 표현된 제약 조건 하에서 각 변수의 최댓값이나 최솟값을 구해야 할 때, 그래프 이론의 최단경로/최장경로 알고리즘을 활용할 수 있다. 이를 차분 제약 시스템(Difference Constraints System)이라 한다.

핵심 원리: 부등식의 방향성

부등식 xi ≤ xj + ck는 정점 j에서 정점 i로 가는 가중치 c_k의 유향 간선으로 해석한다.

문제 유형별 변환 규칙

// 등식
A = B        →  A ≥ B  &&  B ≥ A

// 엄격한 부등식 (정수 범위에서)
A < B        →  B ≥ A + 1
A > B        →  A ≥ B + 1

// 비엄격한 부등식
A ≤ B        →  B ≥ A
A ≥ B        →  A ≥ B + 0

필수 조건: 슈퍼 소스점

모든 정점에 대한 절대적 하한/상한이 필요하다. 예를 들어 xi ≥ C가 주어지면, 가상의 소스점 S=0에서 각 정점 i로 가중치 C의 간선을 연결한다. 이를 슈퍼 소스점이라 한다.

또한 슈퍼 소스점에서 모든 간선에 도달 가능해야 하므로, 그래프의 연결성을 반드시 확인해야 한다.

예제 1: 사탕 분배 (최솟값 → 최장경로)

각 아이에게 최소 몇 개의 사탕을 줘야 하는지 구하는 문제. 모든 조건을 만족하는 최솟값을 구해야 하므로 최장경로로 해결한다.

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

typedef long long ll;

const int MAX_V = 100010;
const int MAX_E = 300010;

int vertexCnt, edgeInput;
int head[MAX_V], to[MAX_E], weight[MAX_E], nxt[MAX_E], edgeIdx;
ll maxDist[MAX_V];
int inQueue[MAX_V], cycleCnt[MAX_V];
bool visited[MAX_V];

void initGraph() {
    memset(head, -1, sizeof(head));
    edgeIdx = 0;
}

void makeEdge(int u, int v, int w) {
    to[edgeIdx] = v;
    weight[edgeIdx] = w;
    nxt[edgeIdx] = head[u];
    head[u] = edgeIdx++;
}

bool longestPath() {
    int front = 0, rear = 1;
    memset(maxDist, 0xc0, sizeof(maxDist));  // -∞
    memset(cycleCnt, 0, sizeof(cycleCnt));
    
    maxDist[0] = 0;
    inQueue[0] = 0;
    visited[0] = true;
    
    while (front != rear) {
        int cur = inQueue[front++];
        if (front == MAX_V) front = 0;
        visited[cur] = false;
        
        for (int i = head[cur]; ~i; i = nxt[i]) {
            int nxtVertex = to[i];
            if (maxDist[nxtVertex] < maxDist[cur] + weight[i]) {
                maxDist[nxtVertex] = maxDist[cur] + weight[i];
                cycleCnt[nxtVertex] = cycleCnt[cur] + 1;
                
                // n+1개 정점(슈퍼 소스 포함)이로 n+1 이상이면 음수/양수 사이클
                if (cycleCnt[nxtVertex] >= vertexCnt + 1) 
                    return false;
                
                if (!visited[nxtVertex]) {
                    inQueue[rear++] = nxtVertex;
                    if (rear == MAX_V) rear = 0;
                    visited[nxtVertex] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> vertexCnt >> edgeInput;
    initGraph();
    
    for (int i = 0; i < edgeInput; i++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {           // A = B
            makeEdge(b, a, 0);
            makeEdge(a, b, 0);
        } else if (type == 2) {    // A < B → B ≥ A+1
            makeEdge(a, b, 1);
        } else if (type == 3) {    // A ≥ B
            makeEdge(b, a, 0);
        } else if (type == 4) {    // A > B → A ≥ B+1
            makeEdge(b, a, 1);
        } else {                    // A ≤ B
            makeEdge(a, b, 0);
        }
    }
    
    // 슈퍼 소스점(0)에서 각 정점으로 최소 1개 조건
    for (int i = 1; i <= vertexCnt; i++) {
        makeEdge(0, i, 1);
    }
    
    if (!longestPath()) {
        cout << -1 << '\n';
    } else {
        ll total = 0;
        for (int i = 1; i <= vertexCnt; i++) total += maxDist[i];
        cout << total << '\n';
    }
    
    return 0;
}

예제 2: 구간 선택 문제 (접두사 합 + 최장경로)

배열에서 각 구간 [a,b]에 대해 최소 c개를 선택해야 할 때, 전체 선택 개수의 최솟값을 구한다. 접두사 합(prefix sum) 기법을 활용한다.

정의: S[i] = 1부터 i까지 선택한 정수의 개수 (S[0] = 0)

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

const int LIMIT = 50001;
const int MAX_N = LIMIT + 10;
const int MAX_E = 150010;

int rangeCount;
int head[MAX_N], to[MAX_E], weight[MAX_E], nxt[MAX_E], edgeIdx;
int longestDist[MAX_N], cycleQueue[MAX_N];
bool inQueue[MAX_N];

void init() {
    memset(head, -1, sizeof(head));
    edgeIdx = 0;
}

void addDirectedEdge(int u, int v, int w) {
    to[edgeIdx] = v;
    weight[edgeIdx] = w;
    nxt[edgeIdx] = head[u];
    head[u] = edgeIdx++;
}

void spfaLongest() {
    memset(longestDist, 0xc0, sizeof(longestDist));
    longestDist[0] = 0;
    
    int front = 0, rear = 0;
    cycleQueue[rear++] = 0;
    inQueue[0] = true;
    
    while (front != rear) {
        int cur = cycleQueue[front++];
        if (front == MAX_N) front = 0;
        inQueue[cur] = false;
        
        for (int i = head[cur]; ~i; i = nxt[i]) {
            int nxtVertex = to[i];
            if (longestDist[nxtVertex] < longestDist[cur] + weight[i]) {
                longestDist[nxtVertex] = longestDist[cur] + weight[i];
                if (!inQueue[nxtVertex]) {
                    inQueue[nxtVertex] = true;
                    cycleQueue[rear++] = nxtVertex;
                    if (rear == MAX_N) rear = 0;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> rangeCount;
    init();
    
    // S[i] - S[i-1] ∈ [0, 1]  (각 정수는 0개 또는 1개 선택)
    for (int i = 1; i <= LIMIT; i++) {
        addDirectedEdge(i - 1, i, 0);    // S[i] ≥ S[i-1] + 0
        addDirectedEdge(i, i - 1, -1);   // S[i-1] ≥ S[i] - 1
    }
    
    // 구간 [a,b]에서 최소 c개 선택: S[b] - S[a-1] ≥ c
    for (int i = 0; i < rangeCount; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a++; b++;  // 1-based 보정
        addDirectedEdge(a - 1, b, c);    // S[b] ≥ S[a-1] + c
    }
    
    spfaLongest();
    cout << longestDist[LIMIT] << '\n';
    
    return 0;
}

사이클 판별의 의미

구현 체크리스트

1. 모든 부등식을 xj ≥ xi + w 형태로 통일
2. 해당 형태에 맞춰 i → j 방향으로 가중치 w의 간선 생성
3. 절대 조건(상수 부등식)은 슈퍼 소스점에서 연결
4. 슈퍼 소스점에서 모든 정점 도달 가능하도록 그래프 보완
5. 최댓값 = 최단경로 / 최솟값 = 최장경로 선택
6. SPFA로 사이클(음수/양수) 탐지하며 결과 계산