P1250 种树（差分约束）
种树 - 洛谷
题目背景
一条街的一边有几座房子，因为环保原因居民想要在路边种些树。
题目描述
路边的地区被分割成块，并被编号成 1, 2, \ldots,n1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。
每个居民都想在门前种些树，并指定了三个号码 bb，ee，tt。这三个数表示该居民想在地区 bb 和 ee 之间（包括 bb 和 ee）种至少 tt 棵树。
居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
输入格式
输入的第一行是一个整数，代表区域的个数 nn。
输入的第二行是一个整数，代表房子个数 hh。
第 33 到第 (h + 2)(h+2) 行，每行三个整数，第 (i + 2)(i+2) 行的整数依次为 b_i, e_i, t_ibi,ei,ti，代表第 ii 个居民想在 b_ibi 和 e_iei 之间种至少 t_iti 棵树。
输出格式
输出一行一个整数，代表最少的树木个数。
输入输出样例
输入 #1复制
941 4 24 6 28 9 23 5 2
输出 #1复制
5
说明/提示
数据规模与约定
对于 100\%100% 的数据，保证：
- 1 \leq n \leq 3 \times 10^41≤n≤3×104，1 \leq h \leq 5 \times 10^31≤h≤5×103。
- 1 \leq b_i \leq e_i \leq n1≤bi≤ei≤n，1 \leq t_i \leq e_i - b_i + 11≤ti≤ei−bi+1。
题解：
算是差分约束模板题了吧，虽然用贪心也能做，但是拓展一下写法总有好处的。差分约束指的是在一系列的不等式方程组中找解满足要求。那么我们可以建图对吧，把约束关系转化为点与点之间的距离，跑SPFA即可。假如是,那么就转化为
,
到
连一条const的路径对吧；建好了之后，1到n跑一遍最长路对吧。为什么是最长路找最小树个数呢？
考虑不走最长路，那么总有x和y点有2种路线，其中我们选择了较短的那一条。那么方程是有约束的啊，x-y最小的就是const，你还选了更短的，是不是违背长边的约束条件了？所以我们建的图必须走最长路，哪怕有一条边短了都会违背长边的约束，否则会互相冲突。最短路的情况一样。
我们用dis表示0点到该点需的最小树个数。此处b和e之间连t的边，而且每个点最多选一次，并且前一个点数量必须比后一个点多，
代码如下：
/*keep on going and never give up*/#includeusing namespace std;#define int long long#define endl "\n" #define pb push_back#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read(){int tep;return scanf("%lld",&tep);}const int maxn=2e6+10;const int mod=1e9+7;const int N=100005;int n,m,to[N],net[N],w[N],dis[N],h[N],cnt;bool vis[N];queueq;void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c;}signed main(){fast cin>>n>>m; int u,v,c; while(m--){ cin>>u>>v>>c; add(u-1,v,c); } for(int i=0;i<=n;i++){ if(i!=0)add(i-1,i,0),dis[i]=-1e12;//前一个点必须不比后一个点少； 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;}