当前位置：首页 > news >正文

算法竞赛备考冲刺必刷题（C++） | 洛谷 P1250 种树

news 2026/7/3 5:11:52

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

撸狗：P1250 种树 - 洛谷

【题目描述】

路边的地区被分割成块，并被编号成1 , 2 , … , n 1, 2, \ldots,n1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码b bb，e ee，t tt。这三个数表示该居民想在地区b bb和e ee之间（包括b bb和e ee）种至少t tt棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

【输入】

输入的第一行是一个整数，代表区域的个数n nn。

输入的第二行是一个整数，代表房子个数h hh。

第3 33到第( h + 2 ) (h + 2)(h+2)行，每行三个整数，第( i + 2 ) (i + 2)(i+2)行的整数依次为b i , e i , t i b_i, e_i, t_ibi,ei,ti，代表第i ii个居民想在b i b_ibi和e i e_iei之间种至少t i t_iti棵树。

【输出】

输出一行一个整数，代表最少的树木个数。

【输入样例】

9 4 1 4 2 4 6 2 8 9 2 3 5 2

【输出样例】

【算法标签】

《洛谷 P1250 种树》 #贪心# #排序# #差分约束#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=30005,M=N*3;// 最大顶点数和边数intn,m;// n: 范围[0,n], m: 区间约束数量inth[N],e[M],w[M],ne[M],idx;// 链式前向星存储图intdist[N];// 最长距离数组boolst[N];// 标记顶点是否在队列中/** * 添加有向边 * @param a 起点 * @param b 终点 * @param c 权重 */voidadd(inta,intb,intc){e[idx]=b;// 边指向的顶点w[idx]=c;// 边的权重ne[idx]=h[a];// 指向原链表头h[a]=idx++;// 更新头指针}/** * SPFA算法求最长路径 * 从顶点0开始，计算到所有顶点的最长路径 */voidspfa(){// 初始化距离为负无穷memset(dist,-0x3f,sizeof(dist));queue<int>q;// SPFA队列q.push(0);// 起点入队st[0]=true;// 标记在队列中dist[0]=0;// 起点距离为0while(!q.empty()){intt=q.front();// 取出队首q.pop();st[t]=false;// 标记不在队列中// 遍历t的所有邻接边for(inti=h[t];i!=-1;i=ne[i]){intj=e[i];// 邻接顶点// 松弛操作：求最长路径if(dist[j]<dist[t]+w[i]){dist[j]=dist[t]+w[i];// 更新最长距离// 如果j不在队列中，入队if(!st[j]){q.push(j);st[j]=true;}}}}}intmain(){// 输入n和区间约束数量mcin>>n>>m;// 初始化邻接表memset(h,-1,sizeof(h));// 添加基础约束边// 顶点编号0~n，共n+1个顶点for(inti=1;i<=n;i++){// 约束1: S_i ≥ S_{i-1}// 即: S_i - S_{i-1} ≥ 0// 建边: i-1 → i，权重0add(i-1,i,0);// 约束2: S_i - S_{i-1} ≤ 1// 即: S_{i-1} - S_i ≥ -1// 建边: i → i-1，权重-1add(i,i-1,-1);}// 添加区间约束for(inti=1;i<=m;i++){intb,e,t;cin>>b>>e>>t;// 约束: S_e - S_{b-1} ≥ t// 即: S_e ≥ S_{b-1} + t// 建边: b-1 → e，权重tadd(b-1,e,t);}// 执行SPFA算法求最长路径spfa();// 输出从0到n的最长路径长度cout<<dist[n]<<endl;return0;}