（未完待续）简单的差分约束系统入门题目。

题目链接：POJ 1201/TYVJ 1415(Joyoi 3230)/LibreOJ 10087/信息学奥赛一本通 T1509/Southwestern Europe 2002。

题目

题目描述

给定 $n$ 个闭区间 $[a _ i,b _ i]$ 和 $c _ i$ 个整数。你需要构造一个整数集合 $\mathbb{Z}$，使得对于任意 $i\in[1,n]$，$\mathbb{Z}$ 中满足$a _ i\leq x\leq b _ i$ 的整数 $x$ 不少于 $c _ i$ 个，求这样的整数集合 $\mathbb{Z}$ 最少包含多少个数。

简而言之就是，从 $0\to 5\times 10^4$ 中选出尽量少的整数，使每个区间 $[a _ i,b _ i]$ 内都有至少 $c _ i$ 个数被选出。

数据范围

对于全部数据，$1\leq n\leq 5\times 10^4,0\leq a _ i\leq b _ i\leq 5\times 10^4,1\leq c _ i\leq b _ i−a _ i+1$。

题解

思路

很明显，我们可以设 $s _ i$ 表示闭区间 $[0,i]$中共有多少个整数。
那么我们可以轻松得出下面两个结论：

1. $0\leq s _ {i+1}-s _ i\leq 1$；
2. $s _ {b _ i}-s _ {a _ {i-1}}\geq c _ i$。

想到关于差分约束系统的知识，我们就可以写程序了。
本题的解法采用形如 $X _ i-X _ j\geq v$ 的约束条件，所以是使用SPFA算法求最长路。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
#include<queue>
using std::queue;
#define INF 0X3F3F3F3F
//以上为头文件
const int MAXN=50000+5;//数据范围最大值
bool inque[MAXN];
int n;
int cnt,head[MAXN],to[MAXN*3],w[MAXN*3],Next[MAXN*3];
int dis[MAXN];
queue<int> Q;
void Add_Edge(int,int,int);
bool SPFA(int);
int main(void){
    register int i,Min=INF,Max=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        static int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        ++a,++b;//防止下标出现负数
        Add_Edge(a-1,b,c);//注意是a-1
        Min=min((int)Min,a-1);
        Max=max((int)Max,b);
    }
    for(i=Min;i<=Max;++i){
        Add_Edge(i,i+1,0);
        Add_Edge(i+1,i,-1);
    }
    SPFA(Min);//这里求的是最长路
    printf("%d\n",dis[Max]);
    return 0;
}
void Add_Edge(int u,int v,int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}
bool SPFA(int s){
    register int i,ID;
    memset(inque,false,sizeof(inque));
    memset(dis,-0X3F,sizeof(dis));//这里求的是最长路
    while(!Q.empty())
        Q.pop();
    inque[s]=true,dis[s]=0;
    Q.push(s);
    while(!Q.empty()){
        ID=Q.front();
        Q.pop();
        inque[ID]=false;
        for(i=head[ID];i;i=Next[i]){
            if(dis[ID]+w[i]>dis[to[i]]){//这里求的是最长路
                dis[to[i]]=dis[ID]+w[i];
                if(!inque[to[i]]){
                    inque[to[i]]=true;
                    Q.push(to[i]);
                }
            }
        }
    }
    return true;//正常（题目保证有解）
}