查分约束不是求最大就是求最小,
1.求最大解
比方说d[0]=0,我么要求在满足约束条件下的所有d[i]最大.我们可以认为开始所有点的d[i]=inf,然后根据约束条件缩小,直到满足所有约束条件;因为是从inf开始缩小的,所以一定是最大解.
memset(dis,inf,sizeof(dis));
dis[0]=0;
spfa();
if(dis[v]>dis[u]+c)
dis[v]=dis[u]+c;
建边时:
      b-a<=c,相当于dis[b]>=dis[a]+c,所以加边e(a,b)=c.
2.求最小解
已知d[0]=0和约束条件,求满足约束下所有点的d[i]最大.那么可以令d[i]=-inf,然后根据约束条件扩大,最后得到最优解.
memset(dis,-inf,sizeof(dis));
dis[0]=0;
spfa();
if(dis[v]<dis[u]+c)
dis[v]=dis[u]+c;
建边时:
      b-a>=c,e(a,b)=c.