POJ - 1716 Integer Intervals（差分約束系統）

POJ - 1716 Integer Intervals（差分約束系統）

題目大意：給出N個區間，要求你找出M個數，這M個數滿足在每個區間都至少有兩個不同的數

解題思路：還是不太懂差分約束系統，數學不太好
借鑒了別人的思路，感覺有點DP思想
設d[i]表示[0,i-1]這個區間有d[i]個數滿足要求
則給定一個區間[a,b]，就有d[b + 1] - d[a] >= 2(b + 1是因為b也算在區間內)
將其轉換為d[a] - d[b + 1] <= -2,這是第一個式子
接著在區間[i,i+1]中滿足
d[i + 1] - d[i] >= 0 轉換為 d[i] - d[i +1] <= 0
d[i + 1] - d[i] <= 1
三個式子構圖
以Max(最右邊界＋1)為源點，進行SPFA
最後答案為d[Max] - d[Min]

#include 
#include 
#include 
using namespace std;    
#define N 10010
#define M 30010
#define INF 0x3f3f3f3f

struct Edge{
    int dist, to, next;
}E[M];

int head[N], d[N], n, tot;
bool vis[N];

void AddEdge(int u, int v, int dist) {
    E[tot].to = v;
    E[tot].dist = dist;
    E[tot].next = head[u];
    head[u] = tot++;
}

void SPFA(int s) {
    for (int i = 0; i <= s; i++) {
        d[i] = INF;
        vis[i] = 0;
    }
    queue q;
    q.push(s);
    d[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (int i = head[u]; i != -1; i = E[i].next) {
            int v = E[i].to;
            if (d[v] > d[u] + E[i].dist) {
                d[v] = d[u] + E[i].dist;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

void solve() {
    memset(head, -1, sizeof(head));
    tot = 0;
    int Min = INF, Max = -INF;
    int u, v;
    for (int i = 0; i < n; i++) {
        scanf(%d%d, &u, &v);
        Min = min(Min, u);
        Max = max(Max, v + 1);
        AddEdge(v + 1, u, -2);
    }

    for (int i = 0; i < Max; i++) {
        AddEdge(i, i + 1, 1);
        AddEdge(i + 1, i, 0);
    }
    SPFA(Max);
    printf(%d
, d[Max] - d[Min]);
}

int main() {
    while (scanf(%d, &n) != EOF) {
        solve();
    }
    return 0;
}