poj 1201-差分約束+spfa

題意： 在區間[0,50000]上有一些整點，並且滿足n個約束條件（u, v, w)，即在區間[u, v]上至少有x個整點，問區間[0, 50000]上至少有幾個整點。
思路：spfa(鄰接表)+差分約束。構造差分約束系統的關鍵：用dict[i]表示區間[0, i]上的整點數，則約束條件可化為dict[v] - dict[u-1] >= w，即dict[v] >= dict[u-1] + w，為spfa求最長路徑。另外還必須挖掘完整兩個隱含的約束條件，這也相當重要，即1 >= dict[i] - dict[i-1] >= 0,（dict[i] >= dict[i-1] + 0(正向邊)和 dict[i-1] - dict[i] >= -1 (反向邊)。因此區間[0, 50000]上至少有幾個整點即為dict[i]的最大值，即dict[max_num]的值。
 
在差分約束系統中如果題目要求是求最小值,就將約束條件轉化為">="形式,然後用Bellman_Ford算法求解約束圖的最長路徑,如果題目要求的是最大值,就將約束條件轉化為"<="形式,然後用Bellman_Ford算法求解約束圖的最短路徑.
代碼：
[cpp] 
#include <stdio.h> 
 
#define maxN 50005//最大邊條數 
#define inf 0x7fffffff//最大距離 
 
struct Edge  
{ 
    int v, w, next; 
}edge[4 * maxN];//邊集 
 
int dis[maxN]; 
bool vis[maxN]; 
int queue[10 * maxN]; 
int preEdge[maxN];//同一個頂點的前一條邊 
 
int edgeNum,n,maxn; 
 
void addEdge(int u, int v, int w)//添加一條邊 
{ 
    edge[edgeNum].v = v; 
    edge[edgeNum].w = w; 
    edge[edgeNum].next = preEdge[u]; 
    preEdge[u] = edgeNum ++; 
} 
 
void spfa()//spaf算法 
{ 
    int head = 0, tail = 1; 
    for (int i = 0; i <= maxn; ++ i) 
    { 
        dis[i] = -inf; 
    } 
    queue[head] = 0; 
    dis[0] = 0; 
    while (head < tail) 
    { 
        int u = queue[head]; 
        vis[u] = true; 
        for (int p = preEdge[u]; p != 0; p = edge[p].next) 
        { 
            int v = edge[p].v; 
            if (dis[v] < dis[u] + edge[p].w) 
            { 
                dis[v] = dis[u] + edge[p].w; 
                if (!vis[v]) 
                { 
                    vis[v] = true; 
                    queue[tail] = v; 
                    tail ++; 
                    /*if (tail == maxN)
                    {
                        tail = 0;
                    }*/ 
                } 
            } 
        } 
        vis[u] = false; 
        head ++; 
        /*if (head == maxN)
        {
            head = 0;
        }*/ 
    } 
} 
 
int main() 
{ 
    scanf("%d", &n); 
    edgeNum = 1; 
    maxn = 0;  www.2cto.com
    while (n --) 
    { 
        int u, v, w; 
        scanf("%d%d%d", &u, &v, &w); 
        if (v + 1 > maxn) 
        { 
            maxn = v + 1; 
        } 
        addEdge(u, v + 1, w); 
    } 
    for (int i = 0; i <= maxn; ++ i) 
    { 
        addEdge(i, i + 1, 0); 
        addEdge(i + 1, i, -1); 
    } 
    spfa(); 
    printf("%d\n", dis[maxn]); 
    return 0; 
}