论：如何生硬的将最少值改成小于的方法走spfa找最短路
先说差分约束在这题的用法
居民想在[a,b]区间内中最少c种棵树
首先要明确：每个区域内最多只能种一棵树
所以用一个数组sum[i]:表示1到i区域至少有多少数
所以sum[i]~sum[i-1]中有0~1棵数,列成不等式就是
sum[i]-sum[i-1]<=1
sum[i-1]-sum[i]<=0
在给定的a到b之间最少有c棵数列成不等式就是
a-b>=c(看到这个是不是很懵,但是在这里它要转换为：b-a<=-c 的形式)
b-a<=-c(因为这题要求最小值)
所以 sum[b]-sum[a-1]<=-c(包括a点本身)
按照这样的关系建链,再用spfa找出最短路径
但是,这题不一定保证所有的点都互相联通,所以要建立一个虚拟根联通所有点,来引导其他点的计算
使所有的点到虚拟根的权值（也就是种树的最少值）为0
sum[n+1]~sum[i]<=0
最后对所求答案ans[n]-min(ans[0~n]),因为差分约束是点与点之间的关系,本题要求答案尽可能的小,所以在不影响原本的点与点的关系的情况下，要缩小最优解
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
struct llk
{
int up;
int zd;
int vis;
}w[maxn*2];
int h[maxn],top,ans[maxn],bj[maxn];
void pop(int next,int end,int viss)
{
w[++top].up=h[next];
w[top].zd=end;
w[top].vis=viss;
h[next]=top;
}
queue<int>mp;
int n;
void spfa(int s)
{
for(int i=0;i<=n+1;i++)
ans[i]=1e9;
bj[s]=1;
ans[s]=0;
mp.push(s);
while(!mp.empty())
{
//cout<<"1"<<endl;
int x=mp.front();
bj[x]=0;
mp.pop();
for(int i=h[x];i!=0;i=w[i].up)
{
int v=w[i].zd;
if(ans[x]+w[i].vis<ans[v])
{
ans[v]=ans[x]+w[i].vis;
if(bj[v]==0)
{
bj[v]=1;
mp.push(v);
}
}
}
}
}
int main()
{
int m,a,b,c,s;
cin>>n>>m;
s=n+1;//虚拟节点
for(int i=0;i<=n;i++)
{
pop(s,i,0);
}
for(int i=1;i<=n;i++)
{
pop(i,i-1,0);
pop(i-1,i,1);
}
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
pop(b,a-1,-c);
}
spfa(s);
int minn=1e9;
for(int i=0;i<=n;i++)
{
//cout<<ans[i]<<" ";
minn=min(minn,ans[i]);
}
//cout<<endl;
cout<<ans[n]-minn;
return 0;
}