题解 P1250 【种树】
浅色调
·
·
题解
Slution：
本题差分约束。。。
对于每个约束条件u\rightarrow 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、0\leq 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\rightarrow u=-1而不是u\rightarrow u+1=1，因为后者直接和u-1\rightarrow u=0冲突了）。
最后spfa跑最长路，输出dis[n]就好了。
### 代码：
```cpp
#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;
}
```