【Codevs 1768】种树 / 题解

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

#include <bits/stdc++.h>
#define maxn 500001
using namespace std;
struct Edge{
    int to,next,val;
}l[maxn*3];
int n,m,k[maxn],head[maxn],dis[maxn],cnt,b[maxn];
void add(int u,int v,int x){
    l[++cnt]=(Edge){v,head[u],x};
    head[u]=cnt;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}
inline void spfa(){
    memset(dis,-127/3,sizeof dis);
    queue<int>q;q.push(0);dis[0]=0;
    while(!q.empty()){
        int u=q.front();q.pop();b[u]=0;
        for(int i=head[u];i;i=l[i].next){
            int v=l[i].to;
            if(dis[v]<dis[u]+l[i].val){
                dis[v]=dis[u]+l[i].val;
                if(!b[v]) b[v]=1,q.push(v); 
            }
        }
    }
}
int main(){
    int x,y,z;
    n=read(),m=read();
    for(int i=1;i<=n;i++) k[i]=read();
    for(int i=1;i<=n;i++) add(i,i+1,0),add(i,i-1,-k[i]);
    for(int i=1;i<=m;i++){
        x=read(),y=read(),z=read();
        add(x-1,y,z);
    }
    add(0,1,0);spfa();
    cout<<dis[n]<<endl;
    return 0;
}