[差分限制] HDU1384 Intervals

差分限制第一題，趕快學了下，這題算是入門題吧，對差分限制有了一點主觀印象。

對于這題，沒看差分限制的知識還是很難想到的，居然能和最長路聯系起來，太玄妙了。

題意：先輸入一個n，然後是n行，一行三個數表示一個範圍[ai, bi]和ci，要求一個數集Z，要求Z和[ai, bi]至少有ci個公共數。

這題如何構造成差分限制系統呢？

差分限制系統有個特點，要包含減法。于是可以利用區間的減法，設d[i]表示[0,i]内包含在Z中的數。

然後就可以寫出不等式了。

d[bi] - d[ai-1] >= ci

除了題目的條件外還有一些條件要加上，就是Z集合的關系。

d[i] - d[i-1] >= 0

d[i] - d[i-1] <= 1    =>   d[i-1] - d[i] >= -1

然後題目要求最小的Z，要像上面這樣把不等号統一乘大于等于，跑一遍最長路。

至于為什麼是大于等于，還不知道，試了一下改成小于等于，然後跑最短路，出來的結果是[min, max]内Z的最大值。

還有些細節，比如ai最小是0，如果減到-1的話數組就越界了，是以把所有條件加一，結果是不會變的。

再比如spfa+STLqueue+STLvector鄰接表，我是跑逾時的。

最近寫網絡流的教訓，已經很少用vector了，有時候queue都手寫，STL效率确實不夠高，被卡時間卡到哭啊。

#include<cstring>
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#define pb push_back
#define pii pair<int,int>
#define LL __int64
#define INF 0x7fffffff
#define LLINF 0x7fffffffffffffff
using namespace std;
const int N =55005;
struct eg{
    int u, v, w;
    eg(){}
    eg(int a, int b, int c) { u = a, v = b, w = c; }
}edg[N<<4];
int fir[N<<4], nex[N<<4], ecnt;
void add(int a, int b, int c){
    edg[ecnt] = eg(a, b, c);
    nex[ecnt] = fir[a], fir[a] = ecnt++;
}
int dis[N];
bool vis[N];
int spfa(int s, int n){
    for(int i = 0 ; i <= n; ++i) dis[i] = -INF, vis[i] = 0;
    queue<int>q;
    dis[s] = 0; vis[s] = 1;
    q.push(s);
    while( !q.empty() ){
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int k = fir[u]; k != -1; k = nex[k]){
            int v = edg[k].v, w = edg[k].w;
            if(dis[v] < dis[u] + w){
                dis[v] = dis[u] + w;
                if( !vis[v] ){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dis[n];
}
int main(){
    int a, b, c, n, l, r;
    while( scanf("%d", &n) != EOF ){
        memset(fir, -1, sizeof(fir));
        l = 50005, r = 0, ecnt = 0;
        for(int i = 0; i < n; ++i){
            scanf("%d %d %d", &a, &b, &c);
            a += 1, b += 1;
            add(a-1, b, c);             // d[b] - d[a-1] >= c
            l = min (a, l);
            r = max (b, r);
        }
        for(int i = l; i <= r; ++i){
            add(i-1, i, 0);             //  d[i] - d[i-1] >= 0
            add(i, i-1, -1);            //  d[i-1] - d[i] >= -1
        }
        printf("%d\n", spfa(l-1, r) );
    }
}