closefrom

引用：

这一题用到了差分约束系统
差分约束系统就是给出一些形如x-y<=b不等式的约束，问你是否有满足问题的解，或者求最小，最大解。
这个问题的神奇之处是可以转化为图论的最短路问题。

一、预备知识：SPFA算法

二、差分约束的转化原理

对于图论的最短路径，有：对于d(v) <= d(u) + w(u, v) ，而差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。

移项得：d(v) – d(u) <= w(u, v)，是不是和上面的x-y<=b的一样？

是的，这就是转化为最短路径算法的原理。

三角不等式： 设dist[v]表示从源点s到v的最短路径长度。对于与v相邻的任意顶点u，dist[v]满足三角不等式：

dist[v] ≤ dist[u] + w(u, v), (其中w(u,v)为边(u, v)的权值)

题目大意：给定n个区间，每个区间中只有一头斑点牛，求最多可能有多少头斑点牛
每个区间最少只有一头斑点牛，也最多只有一头斑点牛
那么一只奶牛要不就是斑点牛，要不就是正常牛，那么就是0<=sum[i]-sum[i-1]<=1
转移一下sum[R]-sum[L-1]<=1,sum[L-1]-sum[R]<=-1
那么就可以差分约束，把i和i-1之间连一条0边，i-1和i之间连一条1边，a-1和b之间连一条1边，b和a-1之间连一条-1边
如何跑一个优秀的spfa才是重点，可以用双向队列优化spfa slf优化

#include <cstdio>
#include <queue>
#define max_n 200005
#define INF 0x3f3f3f3f
using namespace std;
int n,m,cnt=1;
int dis[max_n],first[max_n],vis[max_n];
struct edge{int back,to,cd;}e[max_n*4];
void addedge(int x,int y,int cc){e[++cnt].back=first[x];e[cnt].to=y;e[cnt].cd=cc;first[x]=cnt;}//链式前向星存图
int spfa(){
    deque<int> Q;
    for(int i=1;i<=n;i++)dis[i]=INF;
    Q.push_back(0);
    vis[0]=1;
    while(Q.size()){
        int QmQ=Q.front();Q.pop_front();vis[QmQ]=0;
        for(int i=first[QmQ];i;i=e[i].back){
            if(dis[e[i].to]>dis[QmQ]+e[i].cd){
                dis[e[i].to]=dis[QmQ]+e[i].cd;
                if(!vis[e[i].to]){
                    if(++cnt>1314520)return -1;//梦幻卡时
                    vis[e[i].to]=1;
                    if(Q.size()&&dis[e[i].to]<dis[Q.front()])Q.push_front(e[i].to);//slf优化spfa方法
                    else Q.push_back(e[i].to);
                }
            }
        }
    }
    return dis[n];
}
/*
接下来的全都是基本的spfa模板
*/
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),addedge(x-1,y,1),addedge(y,x-1,-1);
    for(int i=1;i<=n;i++)addedge(i-1,i,1),addedge(i,i-1,0);
    printf("%d",spfa());
    return 0;
}