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