您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 1201 Intervals 區間選點問題：差分約束系統 + SPFA 解法詳解

編輯：C++ 入門

問題描述

給定 n 個閉區間 [aᵢ, bᵢ] 和整數 cᵢ，要求選擇最小的整數集合 Z，使得 Z 與每個區間 [aᵢ, bᵢ] 至少有 cᵢ 個公共元素。n ≤ 50000，座標範圍 0~50000。

差分約束建模

定義前綴和變量 X[k] 表示集合 Z 中 ≤ k 的元素個數。則區間 [l, r] 內至少選 c 個數轉化為：

X[r] - X[l-1] ≥ c ⟹ X[l-1] - X[r] ≤ -c

隱含約束條件

單調性：X[i] ≤ X[i+1] （選點數不減）⟹ X[i] - X[i+1] ≤ 0
步長限制：X[i+1] - X[i] ≤ 1 （每個整數最多選一次）⟹ X[i+1] - X[i] ≤ 1
非負性：X[i] ≥ 0

圖模型構建

每個離散化後的座標作為一個節點
上述不等式轉化為有向邊：X[v] - X[u] ≤ w ⇒ u → v，權重 w
求最小 Z 的大小 = X[max] - X[min] = -dist[min] （從最大節點反向 SPFA）

離散化優化

原座標範圍 0~50000，但實際用到的只有區間端點。將所有 aᵢ 和 bᵢ+1 收集、排序、去重，映射到 0~m-1，節點數從 50001 減少到 ≤ 100000，大幅降低複雜度。

核心代碼實現

#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 2000100;

struct Edge { int u, v, d; Edge(int a=0,int b=0,int c=0):u(a),v(b),d(c){} } e[maxn];
int head[maxn], nxt[maxn], cnt, n;
int dis[maxn], vis[maxn], vt[maxn], index;
map<int, int> mp;

struct Interval { int l, r, value; Interval(int a=0,int b=0,int c=0):l(a),r(b),value(c){} };
vector<Interval> I;

void addEdge(int u, int v, int d) {
    e[cnt] = Edge(u, v, d);
    nxt[cnt] = head[u];
    head[u] = cnt++;
}

void init() {
    I.clear();
    fill(head, head+maxn, -1);
    fill(dis, dis+maxn, INF);
    fill(vis, vis+maxn, 0);
    fill(vt, vt+maxn, 0);
    cnt = 0; index = 0; mp.clear();
}

void readCase() {
    int a, b, c;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        b++;  // 區間右端點 +1 配合前綴和定義
        I.push_back(Interval(a, b, c));
        mp[a] = 0; mp[b] = 0;
    }
    // 離散化映射
    for (auto it = mp.begin(); it != mp.end(); ++it)
        it->second = index++;
    
    // 添加隱含約束邊
    auto it = mp.begin();
    for (int i = 0; i < index-1; i++) {
        int tem = it->first; ++it;
        addEdge(i+1, i, 0);                    // X[i] - X[i+1] ≤ 0
        addEdge(i, i+1, it->first - tem);      // X[i+1] - X[i] ≤ 坐標差
    }
}

bool SPFA(int start) {
    queue<int> q; q.push(start);
    vt[start]++; dis[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 0;
        if (vt[u] > index) return false;  // 負環檢測
        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = e[i].v, d = e[i].d;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                if (!vis[v]) { vis[v] = 1; vt[v]++; q.push(v); }
            }
        }
    }
    return true;
}

void compute() {
    // 添加區間約束邊：X[l-1] - X[r] ≤ -c
    for (auto& inter : I)
        addEdge(mp[inter.r], mp[inter.l], -inter.value);
    
    dis[index-1] = 0;
    SPFA(index-1);
    printf("%d\n", -dis[0]);  // 答案 = X[max] - X[min]
}

int main() {
    while (scanf("%d", &n) != EOF) {
        init(); readCase(); compute();
    }
    return 0;
}