题目描述
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
写一个程序完成以下工作：
输入输出格式
输入格式：
第一行包含数据N，区域的个数(0<N≤30000)；
第二行包含H，房子的数目(0<H≤5000)；
下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。
输出格式：
输出文件只有一行写有树的数目
输入输出样例
Slution：
本题差分约束。。。
对于每个约束条件$u ightarrow v;min = c$，可以理解为$sum[v]-sum[u-1]geq c$（$sum[x]$表示的是$x$的前缀和）。
因为要使最后植的树尽可能的少，所以每个小区间植的树要在满足限制的情况下尽可能的少，于是我们可以罗列出以下约束条件：
1、$sum[v]-sum[u-1]geq c$（表示区间$[u,v]$至少植$c$棵树）
2、$0leq sum[v]-sum[v-1]leq 1$（表示$sum[v]$最多比$sum[v-1]$大$1$）
那么我们按照上述约束条件建图，第一个约束条件令边$w[u,v]=c$表示$sum[v]$比$sum[u]$大$c$，第二个约束条件是闭区间所以建边$w[u+1,u]=-1$和$w[u-1,u]=0$（注意建边方向$u+1 ightarrow u=-1$而不是$u ightarrow u+1=1$，因为后者直接和$u-1 ightarrow u=0$冲突了）。
最后$spfa$跑最长路，输出$dis[n]$就好了。
代码：
#include<bits/stdc++.h> #define il inline #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; const int N=100005,inf=23333333; int n,m,to[N],net[N],w[N],dis[N],h[N],cnt; bool vis[N]; queue<int>q; il int gi(){ int a=0;char x=getchar(); while(x<'0'||x>'9')x=getchar(); while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar(); return a; } il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c;} int main(){ n=gi(),m=gi(); int u,v,c; while(m--){ u=gi(),v=gi(),c=gi(); add(u-1,v,c); } For(i,0,n){ if(i!=0)add(i-1,i,0),dis[i]=-inf; if(i!=n)add(i,i-1,-1); } q.push(0); while(!q.empty()){ int u=q.front();vis[u]=0;q.pop(); for(int i=h[u];i;i=net[i]) if(dis[to[i]]<dis[u]+w[i]){ dis[to[i]]=dis[u]+w[i]; if(!vis[to[i]])q.push(to[i]),vis[to[i]]=1; } } cout<<dis[n]; return 0; }