Intervals-差分约束+SPFA

update@2011-09-17
struct node{int u,v,weight,next;}edge[3*MAX];
int head[MAX];int count = 0;
void add(int u,int v,int c){
    edge[count].u = u;edge[count].v = v;edge[count].weight = c;
    edge[count].next = head[u];head[u] = count++;
}
int SPFA(int  ll,int rr){
    int d[MAX];for(int i = ll;i <= rr;i++){d[i] = -INF;}d[ll] = 0;
    queue<int> my_queue;my_queue.push(ll);
    bool in_queue[MAX] = {};
    while(!my_queue.empty()){
        int start = my_queue.front();my_queue.pop();
        in_queue[start] = false;//拿出来了 所以不在队列中了
        for(int  i = head[start]; i != -1; i = edge[i].next){
            int u = edge[i].u,v = edge[i].v,weight_of_uv = edge[i].weight;
            if(d[v] < d[u] + weight_of_uv){
                d[v] = d[u] + weight_of_uv;
                if(!in_queue[v]){
                    //需要入队且不再队列中
                    my_queue.push(v);in_queue[v] = true;//标记为在队列中
                }
            }
        }
    }
    return d[rr];
}
///main函数主要代码
    int left_most = INF,right_most = -INF;
    memset(head,-1,sizeof(head));
    for(int i = 0;i < N;i++){
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        add(a,b+1,c);
        right_most = mymax(b+1,right_most);
        left_most  = mymin(a,left_most);
    }
    //d[u]-d[v] >= 0 d[u]-d[v] <= 1
    for(int  i = left_most;i < right_most;i++){
        add(i,i+1,0);add(i+1,i,-1);
    }
    printf("%d",SPFA(left_most,right_most));



题目链接:Intervals
SPFA(shortest path faster algorithm)解差分约束。先做一个裸的单源最短路径题熟悉下bellman_ford的思想,然后用队列写SPFA,之后就是根据差分约束建模,求解。 以前看过但自己写的一直过不了,今天终于把邻接表写熟练了 很快搞定....