种树(一道简单的差分约束系统)

2023-10-18 04:40

本文主要是介绍种树(一道简单的差分约束系统),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

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

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

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

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

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

输入

输入文件名为tree.in

输入第1行,包含两个整数nm

第2行,有n个整数ki

第2~m+1行,每行三个整数lirici

输出

输出文件名为tree.out

输出1个整数表示在满足村民全部要求的情况下最少要种的树。村民提的要求是可以全部满足的。

样例输入

tree.in 	 
5 3 
1 1 1 1 1 
1 3 2
4 2 
4 5 1 	 
tree.out
3
 
tree.in 	
 4 3
 3 2 4 1
 1 2 4
 2 3 5
 2 4 6 	 
tree.out
8

样例输出

【输入输出样例解释1】 如图是满足样例的其中一种方案,最少要种3棵树。
【输入输出样例解释2】如图是满足样例的其中两种方案,左图的方案需要种9棵树,右图的方案需要种8棵树。可以验证,最少需要种8棵树。 

提示

【数据范围】


对于30%的数据,0<n≤100,0<m≤100,ki=1;


对于50%的数据,0<n≤2,000,0<m≤5,000,0<ki≤100;


对于70%的数据,0<n≤50,000,0<m≤100,000,0<ki≤1,000;


对于100%的数据,0<n≤500,000,0<m≤500,000,0<ki≤5,000



用s数组表示前缀和,很容易列出不等式s[r[i]]-s[l[i]-1]>=c[i],和s[i]-s[i-1]<=k[i],还有一个比较容易忘记(我就忘了,然后炸飞)s[i]-s[i-1]>=0

看到这一串不等式,差分约束系统就很明显了。移项,得到s[r[i]]>=s[l[i]-1]+c[i],s[i]>=s[i-1]+0,s[i-1]>=s[i]+(-k[i]),根据三角形不等式连变,l[i]-1到r[i]连一条权值为c[i]的边(1<=i<=m),i-1到i连一条权值为0的边(1<=i<=n),i到i-1连一条权值为-k[i]的边(1<=i<=n)。

然后跑最长路SPFA。

附上代码

#include<iostream>  
#include<cstdio>  
#include<cmath>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>  
#include<queue>  
using namespace std;  
int n,m,vet[3000000],Next[3000000],head[1000000],en,b[1000000],s,t;  
bool vis[1000000];  
long long w[3000000],dis[1000000];  
queue<int> Q;  
void addedge(int u,int v,long long val){  en++;  vet[en]=v;  w[en]=val;  Next[en]=head[u];  head[u]=en;  
}  
int main(){  scanf("%d%d",&n,&m);  for(int i=1;i<=n;i++){  long long x;  scanf("%lld",&x);  addedge(i,i-1,-x);  }  for(int i=1;i<=m;i++){  long long z;  int x,y;  scanf("%d%d%lld",&x,&y,&z);  addedge(x-1,y,z);  }  for(int i=0;i<=n;i++)  addedge(n+1,i,0);  for(int i=1;i<=n;i++)addedge(i-1,i,0);//不要忘记s=n+1;  t=n;  vis[s]=true;  b[s]=1;  Q.push(s);  for(int i=0;i<=n;i++)  dis[i]=-1000000000;  while(!Q.empty()){  int u=Q.front();  Q.pop();  vis[u]=false;  for(int i=head[u];i;i=Next[i]){  int v=vet[i];  if(dis[u]+w[i]>dis[v]){  dis[v]=dis[u]+w[i];  b[v]++;  if(!vis[v]){  Q.push(v);  vis[v]=true;  }  }  }  }  printf("%lld\n",dis[t]);  return 0;  
}  


转载于:https://www.cnblogs.com/RetardedZY/p/7469888.html

这篇关于种树(一道简单的差分约束系统)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/230232

相关文章

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

springboot简单集成Security配置的教程

《springboot简单集成Security配置的教程》:本文主要介绍springboot简单集成Security配置的教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录集成Security安全框架引入依赖编写配置类WebSecurityConfig(自定义资源权限规则

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

Linux系统之dns域名解析全过程

《Linux系统之dns域名解析全过程》:本文主要介绍Linux系统之dns域名解析全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、dns域名解析介绍1、DNS核心概念1.1 区域 zone1.2 记录 record二、DNS服务的配置1、正向解析的配置

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis