大致题意:
需要选一些整数点,给出m个约束条件,每个条件表述为,(s,t)表示在从s到t的区间内至少有2个点被选择。求最少选择多少个点。
大致思路:
和poj1201基本相同,在此不再赘述。这道题的点是从0开始取的,要小心数组越界。
详细代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=105000;
const int mMax=10000500;
const int inf=1<<28;
struct{
int v, next;
int w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int stack[nMax],m,sum[nMax];
bool vis[nMax];
void addedge(int a,int b,int w){
edge[k].w = w;
edge[k].v=b;
edge[k].next=head[a];
head[a]=k;k++;
}
bool spfa(int s){
int i, top = 0;
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)dis[i]=-inf;
dis[s]=0;
stack[++top]=s;
vis[s]=true;
while(top){
int u=stack[top--];
for(i=head[u];i!=0;i=edge[i].next){
int v=edge[i].v;
if(dis[v]<dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
if(!vis[v]){
vis[v]=true;
stack[++top] = v;
if(++sum[v]>n)return 0;
}
}
}
vis[u]=false;
}
return 1;
}
int main(){
int m,s,t,c,i,j;
while(scanf("%d",&m)!=EOF){
k=1;
n=-1;
memset(sum,0,sizeof(sum));
memset(head,0,sizeof(head));
while(m--){
scanf("%d%d",&s,&t);
s++,t++;
n=max(n,t);
addedge(s-1,t,2);
}
s=n+2;
for(i=0;i<=n;i++){
addedge(i+1,i,-1);
addedge(i,i+1,0);
}
for(i=0;i<=n;i++){
addedge(s,i,0);
}
spfa(s);
cout<<dis[n]<<endl;
}
return 0;
}
分享到:
相关推荐
iOS版微信抢红包Tweak.zip小程序
该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。
基于springboot社区停车信息管理系统.zip
基于springboot南皮站化验室管理系统源码数据库文档.zip
## 数据指标说明 全要素生产率(TFP)也可以称之为系统生产率。指生产单位(主要为企业)作为系统中的各个要素的综合生产率,以区别于要素生产率(如技术生产率)。测算公式为:全要素生产率=产出总量/全部资源投入量。 数据测算:包含OL、FE、LP、OP、GMM共五种TFP测算方法!数据结果包括excel和dta格式,其中重要指标包括证券代码,固定资产净额,营业总收入,营业收入,营业成本,销售费用,管理费用,财务费用,购建固定资产无形资产和其他长期资产支付的现金,支付给职工以及为职工支付的现金,员工人数,折旧摊销,行业代码,上市日期,AB股交叉码,退市日期,年末是否ST或PT等变量指标分析。文件包括计算方法说明及原始数据和代码。 数据名称:上市公司全要素生产率TFP数据及测算方法(OL、FE、LP、OP、GMM) 数据年份:2000-2023年 数据指标:证券代码、year、TFP_OLS、TFP_FE、TFP_LP1、TFP_OP、TFP_OPacf、TFP_GMM
内容概要:本文详细总结了多种编程语言下常用的算法实现资源,涵盖Python、C++、Java等流行编程语言及其相关的开源平台、在线课程和权威书籍。对于每种语言而言,均提供了具体资源列表,包括开源项目、标准库支持、在线课程及专业书籍推荐。 适合人群:适用于所有希望深入研究并提高特定编程语言算法能力的学习者,无论是编程新手还是有一定经验的技术人员。 使用场景及目标:帮助开发者快速定位到合适的算法学习资料,无论是出于个人兴趣自学、面试准备或是实际工作中遇到的具体算法问题,都能找到合适的解决方案。 其他说明:文中提及多个在线学习平台和社区网站,不仅限于某一特定语言,对于跨学科或多元化技能培养也具有很高的参考价值。
基于springboot的交通旅游订票系统源码数据库文档.zip
内容概要:本文档是一份详细的GO语言教程,涵盖了Go语言的基础语法、数据类型、控制结构、函数、结构体、接口以及并发编程等多个方面。主要内容包括Go语言的基本概念和历史背景、环境配置、基本语法(如变量、数据类型、控制结构)、函数定义与调用、高级特性(如闭包、可变参数)、自定义数据类型(如结构体、接口)以及并发编程(如goroutine、channel、select)等内容。每部分内容都附有具体的代码示例,帮助读者理解和掌握相关知识点。 适合人群:具备一定编程基础的开发者,尤其是希望深入学习和应用Go语言的技术人员。 使用场景及目标:①初学者通过本教程快速入门Go语言;②有一定经验的开发者系统复习和完善Go语言知识;③实际项目开发中利用Go语言解决高性能、高并发的编程问题。 阅读建议:本文档全面介绍了Go语言的各项基础知识和技术细节,建议按章节顺序逐步学习,通过动手实践代码示例加深理解。对于复杂的概念和技术点,可以通过查阅更多资料或进行深入研究来巩固知识。
GEE训练教程
memcached笔记资料,配套视频:https://www.bilibili.com/list/474327672?sid=4486766&spm_id_from=333.999.0.0&desc=1
基于springboot校内跑腿业务系统源码数据库文档.zip
计算机控制光感自动窗帘控制系统设计.doc
基于SpringBoot的校园服务系统源码数据库文档.zip
基于SpringBoot+Vue的美容店信息管理系统源码数据库文档.zip
基于springboot程序设计基础课程辅助教学系统源码数据库文档.zip
这是一个原生的JS网页版斗地主小游戏,代码注释全。带有斗地主游戏基本的地主、选牌、提示、出牌、倒计时等功能。简单好玩,欢迎下载
基于springboot亚运会志愿者管理系统源码数据库文档.zip
该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。
GEE训练教程——Landsat5、8和Sentinel-2、DEM和各2哦想指数下载
基于springboot家校合作平台源码数据库文档.zip