1768 种树 3 时间限制: 2 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 为了绿化乡村，H村积极响应号召，开始种树了。 H村里有n幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上1~n。树就种在房子前面的空地上。 同时，村民们向村长提出了m个意见，每个意见都是按如下格式：希望第li个房子到第ri个房子的房前至少有ci棵树。 因为每个房屋前的空地面积有限，所以每个房屋前最多只能种ki棵树。 村长希望在满足村民全部要求的同时，种最少的树以节约资金。请你帮助村长。 输入描述 Input Description 输入第1行，包含两个整数n，m。 第2行，有n个整数ki。 第3~m+1行，每行三个整数li，ri，ci。 输出描述 Output Description 输出1个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。 样例输入 Sample Input 4 3 3 2 4 1 1 2 4 2 3 5 2 4 6 样例输出 Sample Output 8 数据范围及提示 Data Size & Hint 对于30%的数据，0
/*比较简单的差分约束.但要注意源点的选取. 由约束条件可得(1)dis[y+1]-dis[x]>=z.(2)0<=dis[i]-dis[i-1]<=k[i].因为是跑最长路.所以要把(2)式拆成dis[i]-dis[i-1]>=0.dis[i-1]-dis[i]>=-k[i].spfa松弛即可.*/#include<cstring>#include<cstdio>#include<queue>#define MAXN 500001using namespace std;struct data{int v,next,x;}e[MAXN*3];int n,m,k[MAXN],head[MAXN],dis[MAXN],cut;bool b[MAXN];void add(int u,int v,int x){ e[++cut].v=v; e[cut].x=x; e[cut].next=head[u]; head[u]=cut;}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;}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]=false; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]<dis[u]+e[i].x) { dis[v]=dis[u]+e[i].x; if(!b[v]) b[v]=true,q.push(v); } } } return ;}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<=m;i++) { x=read(),y=read(),z=read(); add(x-1,y,z); } add(0,1,0); for(int i=1;i<=n;i++) add(i,i+1,0),add(i,i-1,-k[i]); spfa(); PRintf("%d",dis[n]); return 0;}新闻热点
疑难解答
