BZOJ 3126 「USACO 2013 · Open」Photo

蒟蒻第一次用差分约束系统（虽然这题可以上 DP）。

设 Si 表示前 i 只牛中斑点牛的个数。
显然有 0≤Si−Si−1≤1。
再根据题目的限制，有 Sbi−Sai−1=1。

前者和后者都可以拆成两个不等式，然后化为 a−b≤c 的形式，即 Si−1−Si≤0Si−Si−1≤1Sbi−Sai−1≤1Sai−1−Sbi≤−1

于是建边跑 SPFA 即可（此题需要用优先队列或是 SLF 优化）（当然你用容错 SLF + mcfx 优化也能过）。

代码：

#include <cstdio>
#include <cstring>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int N = 2e5;
const int M = 1e5;
int n,m;
int to[(N + M << 1) + 5],val[(N + M << 1) + 5],pre[(N + M << 1) + 5],first[N + 5];
inline void add(int u,int v,int w)
{
    static int tot = 0;
    to[++tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot;
}
int dis[N + 5],vis[N + 5],cnt;
struct cmp
{
    inline bool operator()(int a,int b)
    {
        return dis[a] > dis[b];
    }
};
__gnu_pbds::priority_queue<int,cmp> q;
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        add(i,i - 1,0),add(i - 1,i,1);
    int l,r;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&l,&r),add(r,l - 1,-1),add(l - 1,r,1);
    memset(dis,0x3f,sizeof dis),dis[0] = 0,vis[0] = 1,q.push(0);
    int p;
    while(!q.empty())
    {
        vis[p = q.top()] = 0,q.pop();
        for(register int i = first[p];i;i = pre[i])
            if(dis[p] + val[i] < dis[to[i]])
            {
                if(++cnt > 2006312)
                {
                    dis[n] = 0x3f3f3f3f;
                    break;
                }
                dis[to[i]] = dis[p] + val[i];
                if(!vis[to[i]])
                    vis[to[i]] = 1,q.push(to[i]);
            }
    }
    if(dis[n] == 0x3f3f3f3f)
        puts("-1");
    else
        printf("%d\n",dis[n]);
}