Origin

Statement

为了绿化乡村,H村积极响应号召,开始种树了。

H村里有n幢房屋,这些屋子的排列顺序很有特点,在一条直线上。于是方便起见,我们给它们标上1~n。树就种在房子前面的空地上。

同时,村民们向村长提出了m个意见,每个意见都是按如下格式:希望第li个房子到第ri个房子的房前至少有ci棵树。

因为每个房屋前的空地面积有限,所以每个房屋前最多只能种ki棵树。

村长希望在满足村民全部要求的同时,种最少的树以节约资金。请你帮助村长。

Idea

典型的差分约束。令$dis[i]$从第$1$个房子到第$i$个房子的树木总量,约束条件为:
– $0<=dis[i]-dis[i-1]<=k[i]$
– $dis[r_i]-dis[l_i-1]>=c_i$
然后直接建图,SPFA跑一遍。

Code